Depth First Traversal (of DFS) voor een grafiek is vergelijkbaar met Diepte Eerste verplaatsing van een boom . Het enige probleem hier is dat grafieken, in tegenstelling tot bomen, cycli kunnen bevatten (een knooppunt kan twee keer worden bezocht). Om te voorkomen dat een knooppunt meerdere keren wordt verwerkt, gebruikt u een Booleaanse bezochte array. Een grafiek kan meer dan één DFS-traversal hebben.
Voorbeeld:
Invoer: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Uitgang: DFS vanaf hoekpunt 1: 1 2 0 3Invoer: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Uitgang: DFS vanaf hoekpunt 2: 2 0 1 3
Aanbevolen: los het op OEFENING eerst, voordat u verder gaat met de oplossing.
Hoe werkt DFS?
Depth-first search is een algoritme voor het doorkruisen of doorzoeken van boom- of grafiekdatastructuren. Het algoritme begint bij het hoofdknooppunt (waarbij in het geval van een grafiek een willekeurig knooppunt als hoofdknooppunt wordt geselecteerd) en verkent zo ver mogelijk langs elke tak voordat het teruggaat.
Hieronder vindt u de implementatie van de bovenstaande aanpak:
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> |
>
>Uitvoer
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3>
Tijdcomplexiteit: O(V+E) waarbij V het aantal hoekpunten in de grafiek is en E het aantal randen
Hulpruimte: O(V+E)
Raadpleeg het volledige artikel op Diepte eerst zoeken of DFS voor een grafiek voor meer details!