Depth First Traversal (eller DFS) for en graf ligner Dybde Første gennemkørsel af et træ . Den eneste fangst her er, at i modsætning til træer kan grafer indeholde cyklusser (en knude kan besøges to gange). For at undgå at behandle en node mere end én gang skal du bruge en boolsk besøgt matrix. En graf kan have mere end én DFS-gennemgang.
Eksempel:
Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Produktion: DFS fra toppunkt 1: 1 2 0 3
Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Produktion: DFS fra toppunkt 2: 2 0 1 3
Anbefalet: Løs det venligst på ØVE SIG først, inden vi går videre til løsningen.
Hvordan virker DFS?
Dybde-først-søgning er en algoritme til at krydse eller søge i træ- eller grafdatastrukturer. Algoritmen starter ved rodknuden (vælger en vilkårlig knude som rodknude i tilfælde af en graf) og udforsker så langt som muligt langs hver gren, før den går tilbage.
mens loop java
Nedenfor er implementeringen af ovenstående tilgang:
Python3
int til streng konvertering
# 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> |
>
>
java multithreadingProduktion
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3>
Tidskompleksitet: O(V+E) hvor V er antallet af hjørner i grafen og E er antallet af kanter
Hjælpeplads: O(V+E)
Se venligst hele artiklen vedr Depth First Search eller DFS for en graf for flere detaljer!