Depth First Traversal (eller DFS) för en graf liknar Djup Första genomgång av ett träd . Den enda haken här är att, till skillnad från träd, kan grafer innehålla cykler (en nod kan besökas två gånger). För att undvika att bearbeta en nod mer än en gång, använd en boolesk besökt array. En graf kan ha mer än en DFS-traversering.
Exempel:
Inmatning: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Produktion: DFS från vertex 1 : 1 2 0 3Inmatning: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Produktion: DFS från vertex 2: 2 0 1 3
Rekommenderas: Vänligen lös det ÖVA först innan du går vidare till lösningen.
Hur fungerar DFS?
Djup-först-sökning är en algoritm för att korsa eller söka träd- eller grafdatastrukturer. Algoritmen börjar vid rotnoden (väljar någon godtycklig nod som rotnod i fallet med en graf) och utforskar så långt som möjligt längs varje gren innan den backas.
Nedan är implementeringen av ovanstående tillvägagångssätt:
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> |
>
>Produktion
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3>
Tidskomplexitet: O(V+E) där V är antalet hörn i grafen och E är antalet kanter
Hjälputrymme: O(V+E)
Se hela artikeln om Depth First Search eller DFS för en graf för mer detaljer!