Implementierung der Tiefe Erste Suche in C# mit List und Stack in C#

StackOverflow https://stackoverflow.com/questions/5804844

Frage

Ich möchte eine Tiefe erste Suche erstellen, in der ich etwas erfolgreich war.

Hier ist mein bisheriger Code (mit Ausnahme meines Konstruktors, beachten Sie, dass der Scheitelpunkt- und Kantenklassen nur Eigenschaften enthalten, nichts Wichtiges, um hier zu posten):

private Stack<Vertex> workerStack = new Stack<Vertex>();
private List<Vertex> vertices = new List<Vertex>();
private List<Edge> edges = new List<Edge>();

private int numberOfVertices;
private int numberOfClosedVertices;
private int visitNumber = 1;

private void StartSearch()
{
    // Make sure to visit all vertices
    while (numberOfClosedVertices < numberOfVertices && workerStack.Count > 0)
    {
        // Get top element in stack and mark it as visited
        Vertex workingVertex = workerStack.Pop();
        workingVertex.State = State.Visited;

        workingVertex.VisitNumber = visitNumber;
        visitNumber++;

        numberOfClosedVertices++;

        // Get all edges connected to the working vertex
        foreach (Vertex vertex in GetConnectedVertices(workingVertex))
        {
            vertex.Parent = workingVertex;
            workerStack.Push(vertex);
        }
    }
}

private List<Vertex> GetConnectedVertices(Vertex vertex)
{
    List<Vertex> vertices = new List<Vertex>();

    // Get all vertices connected to vertex and is unvisited, then add them to the vertices list
    edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));

    return vertices;
}

Es funktioniert so, wie alle Scheitelpunkte besucht werden, aber nicht in der richtigen Reihenfolge.

Hier ist ein Vergleich, wie meine im Vergleich zu Wikipedia besucht wird:Comparison

Sein scheint meine zu sein und beginnt von rechts nach links.

Weißt du, was es verursacht? (Auch jeder Rat zu meiner Implementierung wäre sehr geschätzt)

Bearbeiten: Ich habe meine Antwort erhalten, wollte aber trotzdem das Endergebnis für die Methode GetConnectedvertices zeigen:

private List<Vertex> GetConnectedVertices(Vertex vertex)
{
    List<Vertex> connectingVertices = new List<Vertex>();

    (from edge in edges
     where edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited
     select edge).
     Reverse().
     ToList().
     ForEach(edge => connectingVertices.Add(edge.VertexTarget));

    return connectingVertices;
}
War es hilfreich?

Lösung

Es scheint, dass meine sich umgedreht wird und von rechts nach links beginnt. Weißt du, was es verursacht?

Wie andere bemerkt haben, drücken Sie die Knoten zu Besuch auf dem Stapel von links nach rechts. Das bedeutet, dass sie von rechts nach links abgelegt werden, da ein Stapel die Bestellung umkehrt. Stapel sind zuletzt zuerst.

Sie können das Problem beheben, indem Sie GetConnectedvertices ein Stapel erstellen, nicht um eine Liste. Auf diese Weise werden die verbundenen Eckpunkte umgekehrt zweimal, einmal, wenn sie auf den zurückgekehrten Stack gehen und einmal, wenn sie auf den echten Stapel gehen.

Auch jeder Rat zu meiner Implementierung wäre sehr geschätzt

Ich nehme an, die Implementierung funktioniert, aber sie hat sehr viele grundlegende Probleme. Wenn ich diesen Code zur Überprüfung präsentieren würde, würde ich Folgendes sagen:

Nehmen wir zunächst an, Sie wollten gleichzeitig zwei Tiefen-First-Suchanfragen dieser Datenstruktur durchführen. Entweder weil Sie es auf mehreren Threads gemacht haben oder weil Sie eine verschachtelte Schleife haben, in der die innere Schleife ein DFS für ein anderes Element als die äußere Schleife durchführt. Was geschieht? Sie stören sich gegenseitig, weil beide versuchen, die Felder "Status" und "VisitNumber" zu mutieren. Es ist eine wirklich schlechte Idee, eine "saubere" Operation zu haben, wie bei der Suche tatsächlich Ihre Datenstruktur "schmutzig" zu machen.

Dies macht es Ihnen auch unmöglich, es zu verwenden anhaltende unveränderliche Daten redundante Teile Ihres Diagramms darstellen.

Außerdem stelle ich fest, dass Sie den Code auslassen, der aufgeräumt wird. Wann wird "Status" jemals auf seinen ursprünglichen Wert zurückgegeben? Was wäre, wenn Sie a zweite DFS? Es würde sofort scheitern, da die Wurzel bereits besucht wird.

Eine bessere Wahl aus all diesen Gründen ist es, den "besuchten" Zustand in seinem eigenen Objekt zu halten, nicht in jedem Scheitelpunkt.

Warum sind alle staatlichen Objekte private Variablen einer Klasse? Dies ist ein einfacher Algorithmus; Es ist nicht nötig, eine ganze Klasse dafür zu erstellen. Eine Tiefe erste Suchalgorithmus sollte das Diagramm für die Suche als formalen Parameter und nicht als Objektzustand nehmen und ihren eigenen lokalen Zustand nach Bedarf in lokalen Variablen und nicht in Feldern beibehalten.

Als nächstes ist die Abstraktion des Diagramms ... nun, es ist keine Abstraktion. Es sind zwei Listen, eine der Eckpunkte und eine der Kanten. Woher wissen wir, dass diese beiden Listen sogar konsistent sind? Angenommen, es gibt Scheitelpunkte, die sich nicht in der Scheitelpunktliste befinden, sondern auf der Kantenliste. Wie verhindern Sie das? Was Sie wollen, ist eine Diagrammabstraktion. Lassen Sie die Diagrammabstraktionsimplementierung sich Sorgen machen, wie die Kanten dargestellt werden und Nachbarn finden.

Als nächstes ist Ihre Verwendung von foreach sowohl legal als auch häufig, aber es macht meinen Kopf weh. Es ist schwer, Ihren Code und den Grund dafür mit allen Lambdas zu lesen. Wir haben eine vollkommen gute Aussage "foreach". Benutze es.

Als nächstes mutieren Sie eine "übergeordnete" Eigenschaft, aber es ist überhaupt nicht klar, wofür diese Eigenschaft ist oder warum es während einer Durchquerung mutiert wird. Scheitelpunkte in einem willkürlichen Diagramm haben nicht "Eltern", es sei denn, es ist ein Baum, und wenn der Diagramm ein Baum ist, müssen der "besuchte" Zustand nicht im Auge behalten. Es gibt keine Schleifen in einem Baum. Was geht hier vor sich? Dieser Code ist nur bizarr und es ist nicht erforderlich, einen DFS durchzuführen.

Als nächstes ist Ihre Helfer -Methode mit dem Namen GetConnectedvertices eine Lüge. Es wird keine angeschlossenen Scheitelpunkte erhalten, sondern auch nicht besuchte Scheitelpunkte angeschlossen. Methoden, deren Namen sehr verwirrend sind.

Schließlich behauptet dies, eine Tiefe zuerst zu sein, aber aber Es sucht nicht nach irgendetwas! Wo wird das Ding gesucht? Wo ist das Ergebnis zurückgegeben? Dies ist überhaupt keine Suche, es ist ein Traversal.

Von vorn anfangen. Was willst du? Eine Tiefe-erste-Durchquerung eines Diagramms mit einem Startscheitelpunkt. Implementieren Sie das dann. Definieren Sie zunächst, was Sie durchqueren. Ein Graph. Welchen Service benötigen Sie aus einer Grafik? Eine Möglichkeit, die benachbarten Eckpunkte zu erhalten:

interface IGraph
{
    IEnumerable<Vertex> GetNeighbours(Vertex v);
}

Was kehrt Ihre Methode zurück? Eine Abfolge von Scheitelpunkten in der Tiefe erster Reihenfolge. Was braucht es? Ein Startscheitel. OK:

static class Extensions
{
    public static IEnumerable<Vertex> DepthFirstTraversal(
        this IGraph graph, 
        Vertex start) 
    { ... }
}

Wir haben jetzt eine triviale Implementierung der ersten Suche in der Tiefe. Sie können jetzt die Where -Klausel verwenden:

IGraph myGraph = whatever;
Vertex start = whatever;
Vertex result = myGraph.DepthFirstTraversal(start)
                       .Where(v=>something)
                       .FirstOrDefault();

OK, wie werden wir diese Methode implementieren, damit sie einen Traversal ohne den Zustand des Diagramms zu zerstören? Pflegen Sie Ihren eigenen externen Zustand:

public static IEnumerable<Vertex> DepthFirstTraversal(
    this IGraph graph, 
    Vertex start) 
{
    var visited = new HashSet<Vertex>();
    var stack = new Stack<Vertex>();

    stack.Push(start);

    while(stack.Count != 0)
    {
        var current = stack.Pop();

        if(!visited.Add(current))
            continue;

        yield return current;

        var neighbours = graph.GetNeighbours(current)
                              .Where(n=>!visited.Contains(n));

        // If you don't care about the left-to-right order, remove the Reverse
        foreach(var neighbour in neighbours.Reverse()) 
            stack.Push(neighbour);
    }
}

Sehen Sie, wie viel sauberer und kürzer das ist? Keine Zustandsmutation. Kein Halten Sie mit Edge -Listen herum. Keine schlecht genannten Helferfunktionen. Und der Code macht tatsächlich das, was er sagt: durchquert ein Diagramm.

Wir erhalten auch die Vorteile von Iteratorblöcken; Wenn jemand dies für eine DF -Suche verwendet, wird die Iteration aufgegeben, wenn die Suchkriterien erfüllt sind. Wir müssen keine vollständige Traversal machen, wenn wir das Ergebnis frühzeitig finden.

Andere Tipps

Ich habe @Erics Code für DFS -Traversal für jeden verallgemeinert T Damit die Dinge für jede Art, die Kinder hat, funktioniert - ich dachte, ich würde teilen:

public static IEnumerable<T> DepthFirstTraversal<T>(
    T start,
    Func<T, IEnumerable<T>> getNeighbours)
{
    var visited = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(start);

    while (stack.Count != 0)
    {
        var current = stack.Pop();

        if (!visited.Add(current))
            continue;

        yield return current;

        var neighbours = getNeighbours(current).Where(node => !visited.Contains(node));

        // If you don't care about the left-to-right order, remove the Reverse
        foreach(var neighbour in neighbours.Reverse())
        {
            stack.Push(neighbour);
        }
    }
}

Beispiel Verwendung:

var nodes = DepthFirstTraversal(myNode, n => n.Neighbours);

Das Problem ist in der Reihenfolge, in der Sie die Elemente durchsuchen. Dein for each in StartSearch garantiert keine Elementreihenfolge. Sie auch nicht FindAll in GetConnectedVertices Methode. Schauen wir uns diese Zeile an:

edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited).ForEach(edge => vertices.Add(edge.VertexTarget));

Sie sollten eine hinzufügen OrderBy() um die gewünschte Bestellung zu gewährleisten.

Die Gegenstände werden in umgekehrter Reihenfolge aus dem Stapel gesteckt, wenn sie darauf gedrückt werden:

stach.push () führt zu: 1 2 3 4 5

stack.pop () führt zu: 5 4 3 2 1 (also: von rechts nach links)

Sie könnten dies genießen:

        public static bool DepthFirstSearch<T>(this IEnumerable<T> vertices, T rootVertex, T targetVertex, Func<T, IEnumerable<T>> getConnectedVertices, Func<T, T, bool> matchFunction = null)
    {
        if (getConnectedVertices == null)
        {
            throw new ArgumentNullException("getConnectedVertices");
        }
        if (matchFunction == null)
        {
            matchFunction = (t, u) => object.Equals(t, u);
        }
        var directlyConnectedVertices = getConnectedVertices(rootVertex);
        foreach (var vertex in directlyConnectedVertices)
        {
            if (matchFunction(vertex, targetVertex))
            {
                return true;
            }
            else if (vertices.DepthFirstSearch(vertex, targetVertex, getConnectedVertices, matchFunction))
            {
                return true;
            }
        }
        return false;
    }

Dies ist meine Implementierung, ein Stapel ist gut genug. Ein Rückwärtsgang erfolgt vor der Foreach -Schleife.

    /// <summary>
    /// Depth first search implementation in c#
    /// </summary>
    /// <typeparam name="T">Type of tree structure item</typeparam>
    /// <typeparam name="TChilds">Type of childs collection</typeparam>
    /// <param name="node">Starting node to search</param>
    /// <param name="ChildsProperty">Property to return child node</param>
    /// <param name="Match">Predicate for matching</param>
    /// <returns>The instance of matched result, null if not found</returns>
    public static T DepthFirstSearch<T, TChilds>(this T node, Func<T, TChilds> ChildsProperty, Predicate<T> Match) 
        where T:class
    {
        if (!(ChildsProperty(node) is IEnumerable<T>))
            throw new ArgumentException("ChildsProperty must be IEnumerable<T>");

        Stack<T> stack = new Stack<T>();
        stack.Push(node);
        while (stack.Count > 0) {
            T thisNode = stack.Pop();
            #if DEBUG
            System.Diagnostics.Debug.WriteLine(thisNode.ToString());
            #endif
            if (Match(thisNode))
                return thisNode;
            if (ChildsProperty(thisNode) != null) {
                foreach (T child in (ChildsProperty(thisNode) as IEnumerable<T>).Reverse()) 
                    stack.Push(child);
            }
        }
        return null;
    }
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top