El uso de Impulso Gráfico para buscar a través de un DAG Gráfica?

Question

Necesito buscar a través de un DAG gráfico, pero no quiero avanzar más allá de un nodo antes de que me han visto todos los otros nodos que han dirigido a los enlaces que apuntan a ella.

Hay un algoritmo existente para manejar esta situación en particular, la profundidad de la primera búsqueda de la respiración y la primera búsqueda no funcionan para este fin de recorrido.

Es decir:

A -> B
B -> C
C -> D
A -> C

No quiero que lleguen a D antes de haber visto tanto B y C.

Answer 1

Así que mis últimos pensamientos son para hacer una clasificación topológica lo largo de todo el gráfico cada vez que se añade o elimina un borde y almacenar el orden de los nodos secundarios inmediatos para ser atravesado para cada nodo (que puede ser un poco de un algoritmo complicado para escribir ).

A continuación hago una amplitud modificada primera búsqueda (como se sugiere por el caos), y en el siguiente BFS pseudo-código, modifique la línea:

for each vertex v in Adj[u]

a ser:

for each vertex v in OrderedAdj[u]

pseudocódigo:

BFS(G, s)
  for each vertex u in V[G]
    color[u] := WHITE 
    d[u] := infinity 
    p[u] := u 
  end for
  color[s] := GRAY 
  d[s] := 0 
  ENQUEUE(Q, s)
  while (Q != Ø) 
    u := DEQUEUE(Q)
    for each vertex v in Adj[u]
      if (color[v] = WHITE)
        color[v] := GRAY 
        d[v] := d[u] + 1  
        p[v] := u  
        ENQUEUE(Q, v)
      else
        if (color[v] = GRAY) 
          ...
        else 
          ...
    end for
    color[u] := BLACK
  end while
  return (d, p)

Creo que esta es la manera más óptima de lograr esto, pero me hace involucrar a escribir mi propio algoritmo BFS recorrido, además de almacenar el orden de los nodos en cada nodo (una sobrecarga en la memoria que se espera evitar), y escribir mi DFS propio visitante para encontrar el orden y almacenar esto en los nodos de la etapa de almacenamiento en caché.

Me sorprende que no hay una manera habitual de hacer esto, sin embargo, ya que me parece una forma bastante común de navegar un gráfico dag ...

Answer 2

Lo que estamos buscando es (1962) algoritmo de clasificación topológica de Kahn. Este no es el algoritmo de clasificación topológica implementado actualmente en BGL, que está basado en DFS, visita todos los vértices, y da salida a los resultados en orden topológico inverso, sino que es muy similar a un BFS y visitas vértices exactamente de la manera que usted describe en su primer párrafo. Usted tiene que escribir el recorrido a sí mismo, pero el algoritmo es sencillo.

Vea el primer algoritmo de clasificación que aparece en la entrada de la Wikipedia topológica: http://en.wikipedia.org/ wiki / Topological_sorting. También vea el Programa 19.8 en Sedgewick de "Algoritmos en C".

Pista 1:. Usar una estructura de datos auxiliar para mantener el número de bordes en para cada vértice, en realidad no hacer el "eliminar borde de gráfico" parte

Pista 2: Para un ejemplo GPLV3'ed de trabajo, se puede echar un vistazo a la aplicación del algoritmo de Kahn en mi proyecto de generación y análisis gráfico de flujo de control CoFlo, en concreto el topological_visit_kahn.h archivo aquí: http://coflo.svn.sourceforge.net/viewvc/coflo /trunk/src/controlflowgraph/topological_visit_kahn.h?view=log

Answer 3

Usted no puede hacer eso con una simple gráfica de recorrido algoritmo debido a que usted está requiriendo que el algoritmo por arte de magia se tiene conocimiento de la estructura de grafo que no puede haber atravesado sin violar sus propios requisitos.Usted tendría que utilizar un enfoque de dos pasos que primero construye hacia atrás de los árboles diciendo que los nodos tienen conexiones de otros nodos, y luego hacer una modificación de la búsqueda en anchura que utiliza la información de el primer paso para retrasar el recorrido, según corresponda.Y tengo la sospecha de que algunas de las estructuras de grafo puede interbloqueo el segundo paso.

Answer 4

¿Qué hay de hacer una ordenación topológica en primer lugar, a continuación, hacer una primera búsqueda en profundidad sobre el gráfico ordenada?

¿Funcionaría?

Answer 5

Cualquier DAG tiene al menos un nodo hoja. La eliminación de cualquier nodo nodo hoja y todos los arcos entrantes deja otra DAG. De forma recursiva, esta menor DAG también tiene al menos un nodo hoja. Al eliminar de forma recursiva todos los nodos de esta manera, con el tiempo el nodo raíz se convierte en un nodo hoja.

Si ahora invierte el orden en el que ha extraído los nodos, tiene un orden de recorrido que tiene las propiedades deseadas. Al visitar nodos hoja pasado, usted garantiza haber visto todos los nodos padre por primera vez.