Diagramos gylis pirmasis apėjimas (arba DFS) yra panašus į Gylis Pirmasis medžio apvažiavimas . Vienintelis dalykas čia yra tas, kad, skirtingai nei medžiai, diagramose gali būti ciklai (mazgas gali būti aplankytas du kartus). Kad mazgas nebūtų apdorotas daugiau nei vieną kartą, naudokite loginį aplankytą masyvą. Diagrama gali turėti daugiau nei vieną DFS perėjimą.
Pavyzdys:
Įvestis: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Išvestis: DFS iš 1 viršūnės: 1 2 0 3Įvestis: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Išvestis: DFS iš 2 viršūnės: 2 0 1 3
Rekomenduojama: išspręskite PRAKTIKA pirma, prieš pereinant prie sprendimo.
Kaip veikia DFS?
Paieška pagal gylį yra medžio ar grafiko duomenų struktūrų perėjimo arba paieškos algoritmas. Algoritmas pradedamas nuo šakninio mazgo (parenkant kokį nors savavališką mazgą kaip šakninį mazgą grafiko atveju) ir kiek įmanoma tyrinėja kiekvieną šaką prieš grįžtant atgal.
Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas:
Python3
# Python3 program to print DFS traversal> # from a given graph> from> collections>import> defaultdict> # This class represents a directed graph using> # adjacency list representation> class> Graph:> ># Constructor> >def> __init__(>self>):> ># Default dictionary to store graph> >self>.graph>=> defaultdict(>list>)> > ># Function to add an edge to graph> >def> addEdge(>self>, u, v):> >self>.graph[u].append(v)> > ># A function used by DFS> >def> DFSUtil(>self>, v, visited):> ># Mark the current node as visited> ># and print it> >visited.add(v)> >print>(v, end>=>' '>)> ># Recur for all the vertices> ># adjacent to this vertex> >for> neighbour>in> self>.graph[v]:> >if> neighbour>not> in> visited:> >self>.DFSUtil(neighbour, visited)> > ># The function to do DFS traversal. It uses> ># recursive DFSUtil()> >def> DFS(>self>, v):> ># Create a set to store visited vertices> >visited>=> set>()> ># Call the recursive helper function> ># to print DFS traversal> >self>.DFSUtil(v, visited)> # Driver's code> if> __name__>=>=> '__main__'>:> >g>=> Graph()> >g.addEdge(>0>,>1>)> >g.addEdge(>0>,>2>)> >g.addEdge(>1>,>2>)> >g.addEdge(>2>,>0>)> >g.addEdge(>2>,>3>)> >g.addEdge(>3>,>3>)> >print>(>'Following is Depth First Traversal (starting from vertex 2)'>)> > ># Function call> >g.DFS(>2>)> # This code is contributed by Neelam Yadav> |
>
>Išvestis
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3>
Laiko sudėtingumas: O(V+E) čia V – grafo viršūnių skaičius, o E – briaunų skaičius
Pagalbinė erdvė: O (V+E)
Peržiūrėkite visą straipsnį apie Pirmoji gylio paieška arba grafiko DFS daugiau detalių!