Algoritam Graph Search temeljna je tehnika u području obrade grafova i pronalaženja informacija. Ovaj algoritam nam omogućuje da pronađemo staze ili komponente u grafu na temelju specifičnih pravila ili algoritama pretraživanja.
Kako radi
- Počnite od određenog vrha(čvora) u grafu.
- Izvršite postupak pretraživanja na temelju određenih pravila, kao što je pretraživanje prvo u dubinu(DFS) ili pretraživanje prvo u širinu(BFS).
- Prelazite po vrhovima i rubovima grafa kako biste tražili cilj ili objekte koje treba pronaći.
- Zabilježite put ili rezultate pretraživanja.
Primjer
Razmotrite sljedeći grafikon:
Želimo pronaći put od vrha A do vrha E u ovom grafu koristeći algoritam pretraživanja prvo u dubinu(DFS).
- Počnite od vrha A.
- Premjestite se na vrh B.
- Nastavite do vrha C.
- Nema susjeda u C, vratite se u vrh B.
- Pomakni se na vrh D.
- Nastavite do vrha A(jer je D povezan s A).
- Premjestite se na vrh B.
- Premjestite se na vrh C.
- Pomakni se na vrh E.
Put od A do E je A -> B -> C -> E.
Primjer koda u C++
U ovom primjeru koristimo DFS algoritam da pronađemo put od vrha A do vrha E na grafu. Rezultat će biti niz vrhova koji tvore put od A do E.