Estoy trabajando en una tarea donde uno de los problemas pide derivar un algoritmo para verificar si un grafo dirigido G = (V, E) está conectado de forma individual (hay como máximo un camino simple desde u hasta v para todos los vértices distintos u, v de V.¿Cuál es la forma más eficiente de determinar si un gráfico dirigido está conectado de forma individual?
Por supuesto que puedes controlarla con fuerza bruta, que es lo que estoy haciendo en este momento, pero quiero saber si hay una manera más eficiente. ¿Podría alguien apuntarme en la dirección correcta?
He leído en otro lugar que la ejecución de DFS una vez en todo el árbol debería ser suficiente. ¿Es necesario correr en cada vértice? – zebraman
realmente no importa. pregunta tonta. – zebraman
Es suficiente repetir para cada vértice no visitado, pero debe volver a recorrer todo el flujo descendente (incluso aquellos marcados como "no visitados"). Por lo tanto, necesitaría las marcas "visitado alguna vez" y "visitado esta vez". –