¿Cómo aprendo el algoritmo de Tarjan?

Question

He estado tratando de aprender el algoritmo de Tarjan de Wikipedia durante 3 horas, pero no puedo entenderlo. :(

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1

¿Por qué es un subárbol del árbol DFS? (DFS en realidad produce un bosque? O_O) Y por qué v.lowlink=v.index implica que v es una raíz?

Por favor alguien puede explicar esto para mí/dar la intuición o la motivación detrás de este algoritmo?

Answer 1

La idea es: al atravesar el árbol, cada vez que ha buscado a través de una rama y está retrocediendo, compruebe si ha encontrado un borde a un nodo 'superior' en el árbol.

• Si no lo hizo (if (v.lowlink = v.index)), entonces usted acaba de completar un SCC - consiste en el nodo actual y todos los nodos de la pila. Eso es exactamente un subárbol del árbol DFS, a excepción de los nodos en los SCC que ya se completaron.

• Si lo hizo, propague esta información a los nodos 'superiores' (v.lowlink := min(v.lowlink, w.lowlink)), porque combinado con la ruta en el árbol DFS, el borde crea una ruta 'hacia arriba'.

DFS produce un bosque, pero siempre se considera un árbol por vez. Siempre se incluye un SCC en un árbol DFS, de lo contrario (al ser un SCC) habría un camino en ambas direcciones entre ambos (todos) los árboles en cuestión; eso es una contradicción.

Answer 2

simplemente agregando a la respuesta de pjotr: v.lowlink es básicamente el índice del nodo superior que has encontrado en el árbol. Tenga en cuenta que más arriba en este contexto significa mínimo a medida que aumenta los índices a medida que avanza. Ahora después de procesar todos sus sucesores, hay básicamente tres casos:

1. v.lowlink < v.index: Esto indica que se ha encontrado un borde posterior. Tenga en cuenta que no hemos encontrado ningún borde posterior, sino uno que apunta a un nodo que está "por encima" del actual. Eso es lo que v.lowlink < v.index implica.

2. v.lowlink = v.index: Lo que sabemos en este caso es que no hay un borde posterior que se refiera a algo sobre el nodo actual. Puede haber un borde posterior para este nodo (lo que significa que uno de sus nodos sucesores w tiene un enlace bajo tal que w.lowlink = v.lowlink = v.index). También podría ser que hubiera un borde posterior que se refiera a algo debajo del nodo actual, lo que significa que había un componente fuertemente conectado debajo del nodo actual que ya se ha impreso. El nodo actual, sin embargo, es definitivamente la raíz de un componente fuertemente conectado también.

3. v.lowlink> v.index: Eso en realidad no es posible. Solo lo estoy enumerando por completo. ;)

Espero que ayude!

Answer 3

Algunos intuición sobre el algoritmo de Tarjan:

• Durante DFS, cuando nos encontramos con un borde posterior de vértice v, actualizamos su ancestro accesible más bajo, es decir que se actualice el valor de baja [v]

• Ahora cuando se procesan todos los bordes salientes de un vértice, es decir, estamos a punto de salir de la llamada DFS para el vértice v, comprobamos el valor de baja [v], ya sea baja [v] == v (Explicación a continuación) . Si no, esto significa que v no es la raíz del SCC y ahora le damos el beneficio al padre de v, es decir, el antecesor alcanzable más bajo del padre [v] ahora se cambia a bajo [v].

Esto suena lógico como si aunque no hay borde posterior directa de los padres [v] para el ancestro de v, pero hay un camino (borde posterior de v + borde hacia v) a través de la cual el padre [v] todavía puede alcanzar al ancestro de v. Por lo tanto, también hemos actualizado el bajo [padre [v]] aquí. Por lo tanto, vamos a seguir actualizando esta cadena y bajo [v] para todos v seguirá actualizando hasta que lleguemos al antecesor (a través de retroceso). Para este ancestro bajo [v] será igual a v. Y así esto actuará como la raíz del SCC.

Esperanza esto ayuda