The in-depth journey of a Graph is to explore the graph by memorizing the summits visited and the path to get there.
The principle and explore the graph from a given summit and one explores all its neighbors going as deep as possible (i.e. repeating the summit operation visited at the summit visited until one is stuck, then one returns via the path taken to the starting point).
The deep path allows to find the tree covering the graph which is not the same in general as the covering tree found via the path in width of the graph.
The algorithm in summary:
Start from the chosen summit to start and mark it.
As long as possible:
- Go to an unvisited neighbour and mark it
- Remember the stop or the arc through which you passed
- If all the neighbours are already visited:
- Back to the top by which it was discovered (backtrack phase: ascent)
If all the tops of the graph are visited (are in the covering tree) then the graph is related otherwise the graph is not related.
Example Python with 3 graphs:
Python module for the in-depth route:
#Parcours in depth of a graph Recursive algorithm: The principle is to explore the graph and retrace your steps when you're stuck. def parcours_en_profondeur (graph, sommet_en_cours:str, sommets_visites:): print ('Try to explore the summit:' ' str(sommet_en_cours)) If sommet_en_cours not in sommets_visites: sommets_visites.append(sommet_en_cours) #Ajoute the current summit at the node visited print ('Exploring the summit:' - str(sommet_en_cours)) sommets_voisins_non_visites for sommet_voisin in graph[sommet_en_cours]: If sommet_voisin not in sommets_visites: sommets_voisins_non_visites.append (sommet_voisin) - Makes a list of nearby summits not yet visited for summit in sommets_voisins_non_visites: #pour all the nearby unvisited peaks are made a deep route parcours_en_profondeur (graph, top, sommets_visites) #Fonction test if the graph is related following an in-depth journey def est_un_graphe_connexe (graph, sommets_visites): if len (sommets_visites) print ("The graph is related") print (20 - "-") else print ("The graph is not related") print (20 - "-") graph ajacence #Liste graph 'A': ['B','C'], 'B': ['A','C', 'D'], 'C': ['D'], 'D':['C','A'] } sommets_visites parcours_en_profondeur (graph,'A',sommets_visites) est_un_graphe_connexe (graphe,sommets_visites) Unrelated graph #Exemple: Top D is not connected to graph graph 'A': ['B','C'], 'B': ['A','C'], 'C': ['A'], 'D': } sommets_visites parcours_en_profondeur (graph,'A',sommets_visites) est_un_graphe_connexe (graphe,sommets_visites) #Autre example graph 'A': , 'B': , 'C': , 'D': } sommets_visites parcours_en_profondeur (graph,'A',sommets_visites) est_un_graphe_connexe (graphe,sommets_visites) #en end of the route if all the peaks are in the summits visited then the graph is related #Note #J're reunited with the indentation errorError: unindent does not match any outer indentation level #Je simply solved it by resuming all the indentation at the beginning of the line #et by replacing it with Tabulation rather than spaces