El viaje en profundidad de un gráfico es explorar el gráfico memorizando las cumbres visitadas y el camino para llegar allí.
El principio y explorar el gráfico de una cumbre dada y uno explora a todos sus vecinos yendo lo más profundo posible (es decir, repitiendo la operación de la cumbre visitada en la cumbre visitada hasta que uno está atascado, entonces uno regresa a través del camino llevado a la punto de partida).
La trayectoria profunda permite encontrar el árbol que cubre el gráfico que no es el mismo en general que el árbol de cobertura encontrado a través de la ruta en ancho del gráfico.
El algoritmo en resumen:
Fase de descenso:
Comience desde la cumbre elegida para comenzar y marcarla.
El mayor tiempo posible:
- Ir a un vecino no visitado y marcarlo
- Recuerda el tope o el arco por el que pasaste
- Si todos los vecinos ya están visitados:
- De vuelta a la parte superior por la que se descubrió (fase de retroceso: ascenso)
Si se visitan todas las tapas del gráfico (están en el árbol de cobertura), entonces el gráfico está relacionado de lo contrario el gráfico no está relacionado.
Ejemplo de Python con 3 gráficos:



Módulo Python para la ruta en profundidad:
#Parcours en profundidad de un gráfico Algoritmo recursivo: El principio es explorar el gráfico y volver a sus pasos cuando está atascado. def parcours_en_profondeur (gráfico, sommet_en_cours:str, sommets_visites[]:): imprimir ('Tratar de explorar la cumbre:' ' str(sommet_en_cours)) Si no sommet_en_cours en sommets_visites: sommets_visites.append(sommet_en_cours) #Ajoute la cumbre actual en el nodo visitado print ('Explorando la cumbre:' - str(sommet_en_cours)) sommets_voisins_non_visites[] para sommet_voisin en gráfic[sommet_en_cours]o: Si no sommet_voisin en sommets_visites: sommets_voisins_non_visites.append (sommet_voisin) - Hace una lista de cumbres cercanas que aún no han sido visitadas para la cumbre en sommets_voisins_non_visites: #pour todos los picos cercanos no visitados se hacen una ruta profunda parcours_en_profondeur (gráfico, parte superior, sommets_visites) #Fonction probar si el gráfico está relacionado después de un viaje en profundidad def est_un_graphe_connexe (gráfico, sommets_visites): si len (sommets_visites) imprimir ("El gráfico está relacionado") impresión (20 - "-") Otro: imprimir ("El gráfico no está relacionado") impresión (20 - "-") gráfico ajacence #Liste Gráfico 'A': ['B','C'], 'B': ['A','C', 'D'], 'C': ['D'], 'D':['C','A'] } sommets_visites[] parcours_en_profondeur (gráfico, 'A',sommets_visites) est_un_graphe_connexe (gráfico,sommets_visites) Gráfico no relacionado #Exemple: La parte superior D no está conectada al gráfico Gráfico 'A': ['B','C'], 'B': ['A','C'], 'C': ['A'], 'D':[] } sommets_visites parcours_en_profondeur (gráfico, 'A',sommets_visites) est_un_graphe_connexe (gráfico,sommets_visites) #Autre ejemplo Gráfico 'A': , 'B': , 'C': , 'D': } sommets_visites parcours_en_profondeur (gráfico, 'A',sommets_visites) est_un_graphe_connexe (gráfico,sommets_visites) #en final de la ruta si todos los picos están en las cumbres visitadas, entonces el gráfico está relacionado #Note #J se reúnen con la sangría errorError: unindent no coincide con ningún nivel de sangría externa #Je simplemente lo resolvió reanudando toda la sangría al principio de la línea #et sustituyéndola por tabulación en lugar de espacios