Viaje en profundidad a través de los gráficos y la implementación de Python en menos de 128 palabras

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:

Ejemplo de gráfico relacionado
Ejemplo de gráfico no relacionado
Ejemplo de gráfico relacionado

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