Depth First Traversal (alebo DFS) pre graf je podobný Hĺbka Prvý prechod stromu . Jediným háčikom je, že na rozdiel od stromov môžu grafy obsahovať cykly (uzol možno navštíviť dvakrát). Ak sa chcete vyhnúť spracovaniu uzla viac ako raz, použite boolovské navštívené pole. Graf môže mať viac ako jeden prechod DFS.
Príklad:
Vstup: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Výkon: DFS z vrcholu 1 : 1 2 0 3
Vstup: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Výkon: DFS z vrcholu 2 : 2 0 1 3
Odporúčané: Vyriešte to ďalej PRAXE najprv pred prechodom na riešenie.
Ako funguje DFS?
Hĺbkové vyhľadávanie je algoritmus na prechádzanie alebo vyhľadávanie stromových alebo grafových dátových štruktúr. Algoritmus začína v koreňovom uzle (v prípade grafu vyberie nejaký ľubovoľný uzol ako koreňový uzol) a pred spätným sledovaním preskúma čo najďalej pozdĺž každej vetvy.
Nižšie je uvedená implementácia vyššie uvedeného prístupu:
znak na reťazec
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> |
>
prepísanie java metódy
>Výkon
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3>
Časová zložitosť: O(V+E) kde V je počet vrcholov v grafe a E je počet hrán
Pomocný priestor: O(V+E)
Pozrite si celý článok na Hĺbkové prvé vyhľadávanie alebo DFS pre graf pre viac detailov!