Algoritmo para comprobar si el grafo dirigido es fuertemente conectado

Question

Necesito comprobar si un grafo dirigido es fuertemente conectado, o, en otras palabras, si todos los nodos puede ser alcanzado por cualquier otro nodo (no necesariamente a través de direct edge).

Una forma de hacerlo es ejecutar un DFS y BFS en cada nodo y ver que todos los demás son todavía accesibles.

Hay un mejor método para hacerlo?

Answer 1

Tarjan's algoritmo de componentes fuertemente conectados (o variación de Gabow ) por supuesto será suficiente; si solo hay un componente fuertemente conectado, entonces el gráfico está fuertemente conectado.

Ambos son tiempo lineal.

Al igual que con una primera búsqueda de profundidad normal, realiza un seguimiento del estado de cada nodo: nuevo, visto pero aún abierto (está en la pila de llamadas), y visto y terminado. Además, almacena la profundidad cuando llega por primera vez a un nodo, y la profundidad más baja a la que se puede acceder desde el nodo (lo sabe después de terminar un nodo). Un nodo es la raíz de un componente fuertemente conectado si la profundidad alcanzable más baja es igual a su propia profundidad. Esto funciona incluso si la profundidad por la cual llega a un nodo desde la raíz no es la mínima posible.

Para verificar si todo el gráfico es un solo SCC, inicie el dfs desde cualquier nodo único, y cuando haya terminado, si la profundidad alcanzable más baja es 0, y se visitó cada nodo, entonces todo el gráfico es fuertemente conectado.

Answer 2

Considere el siguiente algoritmo.

---

1. Empezar en un vértice al azar v de la gráfica G, y ejecutar una DFS(G, v).

   • Si DFS(G, v) no llega a todos los otros vértices en la gráfica G, entonces hay algunos vértice u, de tal manera que no hay ninguna trayectoria de v a u, y así G es no está firmemente conectado.

   • Si lo hace llegar a cada vértice, entonces hay una trayectoria de v a todos los demás vértices en la gráfica G.

2. Invertir la dirección de todas las aristas en el grafo dirigido G.

3. Volver a ejecutar de nuevo un DFS comenzando en v.

   • Si la DFS no llegar a cada vértice, entonces, existe algún vértice u, de tal manera que en la gráfica original no hay ninguna trayectoria de u a v.

   • Por otro lado, si se hace llegar a cada vértice, a continuación, en el gráfico original hay una trayectoria de cada vértice u a v.

Por lo tanto, si G "pasa" tanto DFSs, está fuertemente conectada.Además, desde un DFS se ejecuta en O(n + m) tiempo, este algoritmo se ejecuta en O(2(n + m)) = O(n + m) tiempo, ya que requiere de 2 DFS recorridos.

Answer 3

Para verificar si cada nodo tiene ambas rutas hacia y desde cualquier otro nodo en un gráfico dado:

1. DFS / BFS de todos los nodos:

El algoritmo de Tarjan supone que cada nodo tiene una profundidad d[i]. Inicialmente, la raíz tiene la profundidad más pequeña. Y hacemos las actualizaciones DFS posteriores al pedido d[i] = min(d[j]) para cualquier vecino j de i. En realidad, BFS también funciona bien con la regla de reducción u aquí.

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

Si hay una ruta de reenvío desde v a d[u] <= d[v], entonces d[v] <= d[u] <= d[v]. En el SCC, <=>, por lo tanto, todos los nodos en SCC tendrán la misma profundidad. Para saber si un gráfico es un SCC, verificamos si todos los nodos tienen el mismo <=>.

2. Dos DFS / BFS del nodo único:

Es una versión simplificada del Kosaraju & # 8217; s Algoritmo . Comenzando desde la raíz, verificamos si DFS / BFS puede alcanzar cada nodo. Luego, invierta la dirección de cada borde. Verificamos si cada nodo puede ser alcanzado desde la misma raíz nuevamente. Consulte código C ++ .

Answer 4

Puede calcular la Ruta más corta de todos los pares y ver si alguna es infinita .

Answer 5

El algoritmo de Tarjan ya se ha mencionado. Pero generalmente encuentro que Algoritmo de Kosaraju es más fácil de seguir a pesar de que necesita dos recorridos del gráfico . IIRC, también está bastante bien explicado en CLRS.

Answer 6

test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}

Answer 7

Una forma de hacerlo sería generar la Matriz laplaciana para el gráfico, luego calcule los valores propios y finalmente cuente el número de ceros. El gráfico tiene una fuerte conexión si solo existe un valor propio cero.

Nota: Preste atención al método ligeramente diferente para crear la matriz laplaciana para gráficos dirigidos.

Answer 8

Puede usar el algoritmo simple basado en DFS de Kosaraju & # 8217; que realiza dos recorridos de gráfico DFS:

La idea es que, si se puede llegar a cada nodo desde un vértice v, y cada nodo puede alcanzar v, entonces el gráfico está fuertemente conectado. En el paso 2 del algoritmo, verificamos si todos los vértices son accesibles desde v. En el paso 4, verificamos si todos los vértices pueden alcanzar v (en el gráfico inverso, si todos los vértices son accesibles desde v, entonces todos los vértices pueden alcanzar v en original gráfico).

Algoritmo: 1) Inicialice todos los vértices como no visitados.

2) Realice un recorrido de gráfico DFS a partir de cualquier vértice arbitrario v. Si el recorrido de DFS no & # 8217; visita todos los vértices, devuelva falso.

3) Invierta todos los arcos (o encuentre la transposición o el reverso del gráfico)

4) Marque todos los vértices como no visitados en el gráfico invertido.

5) Realice un recorrido DFS del gráfico invertido a partir del mismo vértice v (igual que el paso 2). Si el recorrido DFS no & # 8217; t visita todos los vértices, entonces devuelve falso. De lo contrario, devuelve verdadero.

Complejidad de tiempo: la complejidad de tiempo de la implementación anterior es la misma que la Búsqueda de profundidad primero que es O (V + E) si el gráfico se representa usando la representación de la lista de adyacencia.