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