C# Graph Traversal

Question

Este algoritmo hace un gran trabajo al atravesar los nodos en un gráfico.

Dictionary<Node, bool> visited = new Dictionary<Node, bool>(); 

Queue<Node> worklist = new Queue<Node>(); 

visited.Add(this, false); 

worklist.Enqueue(this); 

while (worklist.Count != 0) 
{ 
    Node node = worklist.Dequeue(); 

    foreach (Node neighbor in node.Neighbors) 
    { 
     if (!visited.ContainsKey(neighbor)) 
     { 
      visited.Add(neighbor, false); 
      worklist.Enqueue(neighbor); 
     } 
    } 
} 

Puedo usar esto para buscar un nodo de destino en el gráfico. La lista de trabajo elimina (o muestra) los elementos a medida que se procesa la lista de trabajo. Una vez que encuentro el objetivo, ¿cómo puedo devolver la ruta completa al nodo?

Actualización Estoy tratando de encontrar la forma de revertir el camino a la raíz. El método se invoca en el nodo raíz, después de eso, los elementos secundarios pueden tener dos elementos principales, por lo que no es tan simple como llamar a la propiedad principal en cada nodo y realizar una copia de seguridad.

El objetivo del método es encontrar la ruta, no iterar todos los nodos, o verificar si existe un nodo.

Answer 1

Mantenga un registro de los nodos predecesores.En la implementación más sencilla, se trata de un diccionario, y por lo general denota como π en pseudo-códigos:

Dictionary<Node, bool> visited = new Dictionary<Node, bool>(); 
Dictionary<Node, Node> π = new Dictionary<Node, Node>(); 

Queue<Node> worklist = new Queue<Node>(); 

visited.Add(this, false); 

worklist.Enqueue(this); 

while (worklist.Count != 0) 
{ 
    Node node = worklist.Dequeue(); 

    foreach (Node neighbor in node.Neighbors) 
    { 
     if (!visited.ContainsKey(neighbor)) 
     { 
      visited.Add(neighbor, false); 
      π.Add(neighbor, node); 
      worklist.Enqueue(neighbor); 
     } 
    } 
} 

A continuación, puede iterar a través de estos predecesores que dar marcha atrás el camino desde cualquier nodo, digamos e:

while (π[e] != null) { 
    Console.WriteLine(e); 
    e = π[e]; 
} 

Answer 2

¿Es "esto", es decir, la instancia actual, la "raíz" del gráfico, si existe tal cosa?

¿El gráfico es cíclico o acíclico? Me temo que no conozco todos los términos para la teoría de grafos.

Esto es lo que realmente me pregunto acerca de:

A -> B -> C ------> F 
    B -> D -> E -> F 

Aquí están mis preguntas:

• ocurrirá esto?
• ¿Puede "esto" en su código comenzar en B?
• ¿Cuál será el camino a F?

Si el gráfico nunca vuelve a unirse cuando se ha dividido, no contiene ciclos, y "esto" siempre será la raíz/inicio del gráfico, un diccionario simple manejará la ruta.

Dictionary<Node, Node> PreNodes = new Dictionary<Node, Node>(); 

para cada nodo que visite, agregue el nodo vecino como clave y el nodo del que era vecino como valor. Esto le permitirá, una vez que encuentre el nodo objetivo, retroceder para obtener la ruta invertida.

En otras palabras, el diccionario de la gráfica anterior, después de un recorrido completo sería:

B: A 
C: B 
D: B 
E: D 
F: C (or E, or both?) 

Para encontrar la ruta de acceso al E-nodo, simplemente dar marcha atrás:

E -> D -> B -> A 

Qué le da la ruta:

A -> B -> D -> E 

Answer 3

Dado que no está rastreando la ruta al nodo "actual" en todo momento, lo hará tiene que construir eso cuando hayas encontrado el objetivo. Si su clase Node tiene una propiedad Parent, puede retroceder fácilmente al árbol para construir la ruta completa.

Answer 4

Peter es casi correcto. No creo que pueda almacenar un enlace al vértice principal en la clase de nodo, ya que cambia según el vértice en el que inicie su primera búsqueda de amplitud. Debe crear un Diccionario principal con las claves como nodos y los valores como nodos principales. A medida que visita cada vértice (pero antes del procesamiento) agrega los padres al diccionario. Luego puede caminar por el camino principal hasta el vértice raíz.

Answer 5

He intentado usar este fragmento para obtener los caminos alternativos a partir de vértice (vértices en mi código), mediante la fuente y el destino, sino que simplemente no trabajan ...

public String EncontrarMenorCaminho(Vertice o, Vertice d) 
     { 
      Dictionary<Vertice, bool> visited = new Dictionary<Vertice, bool>(); 
      Dictionary<Vertice, Vertice> previous = new Dictionary<Vertice, Vertice>(); 
      Queue<Vertice> worklist = new Queue<Vertice>(); 
      String operacao = "Registro de operações realizadas:\r\n\r\n"; 

      visited.Add(o, false); 
      worklist.Enqueue(o); 
      while (worklist.Count != 0) 
      { 
       Vertice v = worklist.Dequeue(); 
       foreach (Vertice neighbor in EncontrarVizinhos(v)) 
       { 
        if (!visited.ContainsKey(neighbor)) 
        { 
         visited.Add(neighbor, false); 
         previous.Add(neighbor, v); 
         worklist.Enqueue(neighbor); 
        } 
       } 
      } 

      if (previous.Count > 0) 
      { 
       for (int p = 0; p < previous.Count; p++) 
       { 
        Vertice v1 = previous.ElementAt(p).Key; 
        Vertice v2 = previous.ElementAt(p).Value; 
        EncontrarAresta(v1, v2).Selecionado = true; 
        EncontrarAresta(v2, v1).Selecionado = true; 
        operacao += v1.Info.ToString() + "x" + v2.Info.ToString() + "\r\n"; 
       } 
      } 

      List<Vertice> grupos = new List<Vertice>(); 

      foreach (Aresta a in ArestasSelecionadas()) 
      { 
       if (!grupos.Contains(a.Origem)) grupos.Add(a.Origem); 
      } 

      foreach (Vertice v in grupos) 
      { 
       int menorpeso = this.infinito; 
       foreach(Vertice vz in EncontrarVizinhos(v)) 
       { 
        Aresta tmp = EncontrarAresta(v,vz); 
        if (tmp.Selecionado == true && tmp.Peso < menorpeso) 
        { 
         menorpeso = tmp.Peso; 
        } 
        else 
        { 
         tmp.Selecionado = false; 
        } 
       } 

      } 




      DesenharMapa(); 

      return operacao; 

Básicamente la operación es conseguir todos marcados bordes (selecionado = true) y comprobar de nuevo si es necesario siga seleccionada ...

En esta muestra, que quieren obtener la ruta más corta desde vertext 'N' al vértice 'Q':

Vea una imagen de vista previa aquí: