Traversal de gráfico dirigido cíclico

Question

I tiene un gráfico cíclico dirigido. A partir de las hojas, deseo de datos Propagar unidos a cada nodo de aguas abajo a todos los nodos que son alcanzables a partir de ese nodo. En particular, tengo que seguir empujando los datos alrededor de los ciclos que se alcanzan hasta que los ciclos se estabilicen.

estoy completamente seguro de que este es un problema transversal de la gráfica. Sin embargo, estoy teniendo un poco de dificultad para tratar de encontrar un algoritmo adecuado --- Creo que me falta unos cruciales palabras clave de búsqueda.

Antes de intentar escribir mi propio algoritmo a medias O (n ^ 3), me puede apuntar cualquier persona en una solución adecuada? Y lo que este problema particular llamado?

Answer 1

Como la gráfica es cíclico (es decir, puede contener ciclos), I sería primero descomponerlo en componentes fuertemente conectados. A conectado fuertemente componente de un grafo dirigido es un subgrafo donde cada nodo es accesible desde todos los demás nodos en el mismo subgrafo. Esto produciría un conjunto de subgrafos. Tenga en cuenta que un componente fuertemente conectado de más de un nodo es efectivamente un ciclo.

Ahora, en cada componente, cualquier información en un nodo finalmente terminar en todos los demás nodos del gráfico (ya que son todos accesibles). Así, para cada subgrafo podemos simplemente tomar todos los datos de todos los nodos en ella y hacer que cada nodo tiene el mismo conjunto de datos. No hay necesidad de seguir adelante a través de los ciclos. También, al final de este paso, todos los nodos en el mismo componente contiene exactamente los mismos datos.

El siguiente paso sería la de contraer cada componente fuertemente conectado en un solo nodo. A medida que los nodos dentro del mismo componente todos tienen los mismos datos, y por lo tanto son básicamente los mismos, esta operación no cambia la gráfica. El "nodo super" recién creado heredará todas las aristas de salir o entrar en los nodos del componente de nodos fuera del componente.

Puesto que hemos colapsado todos los componentes fuertemente conectados, no habrá ciclos en la gráfica resultante (¿Por qué? Porque si hubiera habido un ciclo formado por los nodos resultantes, todos ellos se han colocado en el mismo componente en el primer lugar ). El gráfico resultante es ahora un Dirigido acíclicos Gráfico . No hay ciclos, y un simple profundidad primero recorrido de todos los nodos con grado de entrada = 0 (es decir nodos que no tienen bordes entrantes), la propagación de datos de cada nodo a sus nodos adyacentes (es decir, sus "niños"), debe realizar el trabajo .