¿Cuál es la forma más eficiente de determinar si un gráfico dirigido está conectado de forma individual?

Question

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.

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?

Answer 1

Ha intentado DFS.

Run DFS for every vertex in the graph as source 
    If a visited vertex is encountered again, the graph is not singly connected 
repeat for every unvisited vertex. 
The graph is singly connected. 

complejidad O (v^2), o (v) como DFS no representante etition.

Answer 2

Hay una mejor respuesta para esta pregunta. puedes hacer eso en O (| V |^2). y con más esfuerzo puedes hacerlo en tiempo lineal.

En primer lugar, encontrar los componentes de G. conectado firmemente en cada componente fuerte, se busca encontrar estos casos: 1) si hay un borde delantero en este componente, que no está conectada por separado, 2) si hay un borde cruzado en este componente, no está conectado por separado, 3) si hay al menos dos bordes posteriores en un árbol enraizado en el vértice u, ante ancestros propios de u, entonces no está conectado solo.

esto se puede hacer en O (E). (Creo que a excepción del caso 3. ¡No pude implementarlo bien!).

Si no se produjo ninguno de los casos anteriores, debe comprobar si hay un borde cruzado o un borde anterior en G^SCC (gráfico G, con componentes fuertes reemplazados por nodos individuales), ya que no tenemos se puede hacer repitiendo dfs en cada vértice de este gráfico en O (| V |^2).

Answer 3

Ejecute DFS una vez desde cada vértice. El gráfico solo está conectado si y solo si no hay bordes hacia adelante y no hay bordes transversales dentro de un componente .

Complejidad: O (VE)

Answer 4

No estoy de acuerdo que su complejidad será O (V^2), como en la SSE que no lo llamamos para cada vértice que ver en la Introducción al libro de algoritmos también, la sintaxis es DFS (G). Solo llamamos a DFS para un gráfico completo, no para un solo vértice a diferencia de BFS. Entonces aquí, en este caso, según yo, debemos verificarlo llamando a DFS una vez. Si se encuentra nuevamente un vértice visitado, el gráfico no está conectado por separado (definitivamente tenemos que llamarlo para cada componente desconectado pero ya incluido en el código) ASÍ QUE la complejidad será O (V + E). Como aquí E = V, la complejidad debe ser O (V).

Answer 5

Pensé en esto: 1) Ejecutar DFS desde cualquier vértice, si todos los vértices están cubiertos en el DFS sin bordes anteriores (no puede haber cruz porque de lo contrario no se cubrirán todos los vértices), entonces puede ser un candidato potencial.

2) Si un vértice (nivel j) que se encuentra en el DFS tiene un borde posterior al nivel i, entonces ningún otro vértice encontrado debe tener un borde posterior hacia cualquier vértice con un nivel menor que j y cada vértice mucho ser alcanzable a la raíz (verificada con el segundo DFS).

Esto lo hace en tiempo lineal si esto es correcto.

Answer 6

Lea this one. Realmente lo explica bien.

Answer 7

Eche un vistazo a la definición de simple path.Un gráfico cíclico puede conectarse individualmente. DFS no funcionará para A->B, B->A, que está conectado de forma individual.

El siguiente artículo usa componentes fuertemente conectados para resolver esto.

https://www.cs.umd.edu/~samir/grant/khuller99.ps