Recorrido del gráfico C #

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 encontrar un nodo objetivo 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 encuentre el objetivo, ¿cómo puedo devolver la ruta completa al nodo?

Actualizar Estoy tratando de descubrir cómo invertir el camino a la raíz. El método se llama en el nodo raíz, después de eso, los niños pueden tener dos padres, por lo que no es tan simple como llamar a la propiedad padre en cada nodo y recorrer de nuevo.

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 fácil, este es un diccionario, y generalmente se denota como p en pseudocó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);
        }
    }
}

Luego puede iterar a través de estos predecesores para realizar un seguimiento de la ruta desde cualquier nodo, por ejemplo e :

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

Answer 2

Intenté usar este fragmento para obtener las rutas alternativas desde el vértice (vértices en mi código), usando el origen y el destino, pero simplemente no funciona ...

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 consiste en obtener todos los bordes marcados (Selecionado = true) y verificar nuevamente si es necesario continuar seleccionado ...

En esta muestra, quiero obtener la ruta más corta del vértice 'N' al vértice 'Q':

Vea una imagen de vista previa aquí:

Answer 3

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 de la teoría de grafos.

Esto es lo que realmente me pregunto:

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

Aquí están mis preguntas:

• ¿Esto ocurrirá?
• ¿Puede " esto " ¿Alguna vez tu código comienza en B?
• ¿Cuál será el camino hacia F?

Si el gráfico nunca se vuelve a unir 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 de destino, retroceder para obtener la ruta invertida.

En otras palabras, el diccionario para el gráfico 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 al nodo E, simplemente retroceda:

E -> D -> B -> A

Que te da el camino:

A -> B -> D -> E

Answer 4

Dado que no está rastreando la ruta a la " actual " Nodo en todo momento tendrá que construirlo cuando haya encontrado el objetivo. Si su clase Node tiene una propiedad Parent, podría retroceder fácilmente el árbol para construir la ruta completa.

Answer 5

Peter está casi en lo correcto. No creo que pueda almacenar un enlace al vértice principal en la clase de nodo, porque cambia según el vértice en el que comienza su 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 la ruta principal de regreso al vértice raíz.