Depth First Traversal (o DFS) per a un gràfic és similar a Profunditat Primera travessa d'un arbre . L'únic problema aquí és que, a diferència dels arbres, els gràfics poden contenir cicles (un node es pot visitar dues vegades). Per evitar processar un node més d'una vegada, utilitzeu una matriu booleana visitada. Un gràfic pot tenir més d'un recorregut DFS.
preparar-se per a la prova mockito
Exemple:
Entrada: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Sortida: DFS del vèrtex 1 : 1 2 0 3Entrada: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Sortida: DFS del vèrtex 2 : 2 0 1 3
Recomanat: si us plau, resol-ho PRÀCTICA primer, abans de passar a la solució.
Com funciona DFS?
La cerca en profunditat és un algorisme per recórrer o cercar estructures de dades d'arbre o gràfic. L'algoritme comença al node arrel (seleccionant algun node arbitrari com a node arrel en el cas d'un gràfic) i explora el més lluny possible al llarg de cada branca abans de retrocedir.
A continuació es mostra la implementació de l'enfocament anterior:
Python 3
# 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> |
>
>Sortida
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3>
Complexitat temporal: O(V+E) on V és el nombre de vèrtexs del gràfic i E és el nombre d'arestes
Espai auxiliar: O(V+E)
Consulteu l'article complet sobre Cerca en profunditat o DFS per a un gràfic per a més detalls!