Depth First Traversal (nebo DFS) pro graf je podobný Hloubka První přejezd stromu . Jediný háček je v tom, že na rozdíl od stromů mohou grafy obsahovat cykly (uzel lze navštívit dvakrát). Chcete-li se vyhnout zpracování uzlu více než jednou, použijte booleovské navštívené pole. Graf může mít více než jedno procházení DFS.
Příklad:
Vstup: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Výstup: DFS z vrcholu 1 : 1 2 0 3Vstup: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Výstup: DFS z vrcholu 2 : 2 0 1 3
Doporučeno: Vyřešte to na PRAXE nejprve, než přejdete k řešení.
Jak DFS funguje?
Hloubkové vyhledávání je algoritmus pro procházení nebo prohledávání stromových nebo grafových datových struktur. Algoritmus začíná v kořenovém uzlu (v případě grafu vybere nějaký libovolný uzel jako kořenový uzel) a prozkoumá co nejdále podél každé větve, než se vrátí zpět.
Níže je uvedena implementace výše uvedeného přístupu:
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> |
>
>Výstup
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3>
Časová náročnost: O(V+E) kde V je počet vrcholů v grafu a E je počet hran
Pomocný prostor: O(V+E)
Přečtěte si prosím celý článek na Hloubkové první vyhledávání nebo DFS pro graf Více podrobností!