C # Graph Traversal

Question

Dieser Algorithmus hat eine große Aufgabe der Knoten in einem Graphen durchlaufen.

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);
        }
    }
}

Das kann ich verwenden, um einen Zielknoten in der Grafik zu finden. Die Arbeitsliste entnimmt (oder POP) die Einzelteile als die Arbeitsliste wird abgearbeitet. Sobald ich das Ziel finden, wie kann ich den vollständigen Pfad zum Knoten zurückkehren?

Aktualisieren Ich versuche, herauszufinden, wie man den Pfad zur Wurzel umkehren. Das Verfahren ist auf dem Wurzelknoten genannt, nach, dass Kinder zwei Eltern haben kann, so ist es nicht so einfach wie auf jedem Knoten die übergeordnete Eigenschaft aufrufen und durchqueren wieder nach oben.

Das Ziel des Verfahrens ist es, den Weg zu finden, die nicht alle Knoten zu durchlaufen, oder zu überprüfen, ob ein Knoten vorhanden ist.

Answer 1

Verfolgen Sie die Vorgängerknoten. In der einfachsten Ausführung ist dies ein Wörterbuch, und in der Regel als π in pseudo-Codes bezeichnet:

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);
        }
    }
}

Dann können Sie diese Vorgänger durchlaufen den Weg von jedem Knoten einen Rückzieher, sagen e:

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

Answer 2

Ich verwende diese Schnipsel versuchte, die alternativen Wege zur Spitze (Scheitelpunkte in meinem Code) zu erhalten, unter Verwendung von Quelle und Schicksal, sondern einfach nicht funktionieren ...

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;

Basicly die Operation alle markierten Kanten bekommen (Selecionado = true) und erneut zu überprüfen, wenn nötig ist weiterhin gewählt ...

In diesem Beispiel möchte ich den kürzesten Weg bekommen von vertext 'N' Vertex 'Q':

ein Vorschaubild Siehe hier:

Answer 3

Ist „die“, das heißt, die aktuelle Instanz, die „Wurzel“ des Graphen, wenn es so etwas überhaupt?

Ist der Graph zyklisch oder azyklisch? Ich fürchte, ich weiß nicht, alle Bedingungen für die Graphentheorie.

Hier ist, was ich wirklich über mich fragen:

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

Hier sind meine Fragen:

• Wird diese auftreten?
• Kann "this" in Ihrem Code jemals bei B starten?
• Was wird der Weg zum F sein?

Wenn der Graph nie wieder miteinander verbindet, wenn es aufgespalten hat, keine Zyklen enthält, und „dies“ immer die Wurzel / Start des Graphen, ein einfaches Wörterbuch den Pfad behandelt.

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

für jeden Sie Knoten besuchen, fügen Sie den benachbarten Knoten als Schlüssel, und der Knoten war es ein Nachbar als Wert. Dies ermöglicht es Ihnen zu, wenn Sie den Zielknoten finden haben, wieder einen Rückzieher den umgekehrten Weg zu erhalten.

Mit anderen Worten, das Wörterbuch für das Diagramm oben, nach einer vollständigen Traversal wäre:

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

Um den Pfad zu den E-Knoten zu finden, einfach Rückzieher:

E -> D -> B -> A

Was gibt Ihnen den Weg:

A -> B -> D -> E

Answer 4

Da Sie nicht den Pfad zum „aktuellen“ Knoten jederzeit Tracking müssen Sie konstruieren, dass, wenn Sie das Ziel gefunden zu haben. Wenn Ihre Klasse Node eine Parent-Eigenschaft haben könnte man leicht den Baum wieder ansetzen, um den vollständigen Pfad zu konstruieren.

Answer 5

Peter ist fast richtig. Ich glaube nicht, dass Sie einen Link zu dem übergeordneten Knoten in der Knotenklasse speichern können, weil sie in Abhängigkeit von dem Scheitelpunkt ändern, an den Sie Ihre Breitensuche starten. Sie benötigen einen Elternteil Wörterbuch mit den Tasten Knoten erstellen sind und die Werte übergeordneter Knoten zu sein. Wie Sie jede Ecke besuchen (aber vor der Verarbeitung), um die Eltern zum Wörterbuch hinzufügen. Dann können Sie den übergeordneten Pfad zurück zu dem Wurzelknoten zu Fuß auf.