Algoritem Graph Search je temeljna tehnika na področju obdelave grafov in iskanja informacij. Ta algoritem nam omogoča iskanje poti ali komponent v grafu na podlagi določenih pravil ali iskalnih algoritmov.
Kako deluje
- Začnite z določene točke(vozlišča) v grafu.
- Izvedite postopek iskanja na podlagi posebnih pravil, kot je iskanje najprej v globino(DFS) ali iskanje najprej v širino(BFS).
- Prečkajte oglišča in robove grafa, da poiščete cilj ali predmete, ki jih želite najti.
- Zabeležite pot ali rezultate iskanja.
Primer
Razmislite o naslednjem grafu:
V tem grafu želimo najti pot od točke A do točke E z algoritmom iskanja najprej v globino(DFS).
- Začnite pri točki A.
- Premakni se na točko B.
- Nadaljujte do točke C.
- V C ni sosedov, vrnite se do tocke B.
- Premakni se na točko D.
- Nadaljujte do oglišča A(kot je D povezano z A).
- Premakni se na točko B.
- Premakni se na točko C.
- Premakni se na točko E.
Pot od A do E je A -> B -> C -> E.
Primer kode v C++
V tem primeru uporabljamo algoritem DFS za iskanje poti od točke A do točke E v grafu. Rezultat bo zaporedje vozlišč, ki tvorijo pot od A do E.