webentwicklung-frage-antwort-db.com.de

Tiefe implementieren Erste Suche in C # mit List und Stack

Ich möchte eine Tiefensuche erstellen, bei der ich etwas erfolgreich war.

Hier ist mein Code bis jetzt (Außer meinem Konstruktor, beachten Sie, dass die Klassen Vertex und Edge nur Eigenschaften enthalten.

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, dass alle Knoten besucht werden, jedoch nicht in der richtigen Reihenfolge.

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

Es scheint, dass meine umgedreht ist und von rechts nach links beginnt.

Wissen Sie, was es verursacht? (Auch jeder Hinweis zu meiner Umsetzung wäre sehr dankbar)

Vielen Dank

EDIT: Ich habe meine Antwort erhalten, wollte aber trotzdem das Endergebnis für die GetConnectedVertices-Methode anzeigen:

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;
}
27
Dumpen

Es sieht so aus, als ob meine gedreht ist und von rechts nach links beginnt. Wissen Sie, was es verursacht? 

Wie andere bereits bemerkt haben, schieben Sie die Node-to-Visit-Next-Reihenfolge auf dem Stapel in der Reihenfolge von links nach rechts. Das heißt, sie werden von rechts nach links abgeworfen, da ein Stapel die Reihenfolge umkehrt. Stapel sind Last-in-First-Out.

Sie können das Problem beheben, indem Sie GetConnectedVertices einen Stapel und keine Liste erstellen lassen. Auf diese Weise werden die verbundenen Scheitelpunkte zweimal umgekehrt, einmal, wenn sie sich auf dem zurückgegebenen Stapel befinden, und einmal, wenn sie sich auf dem realen Stapel befinden.

Auch jeder Rat zu meiner Umsetzung wäre sehr dankbar

Ich denke, die Implementierung funktioniert, aber sie hat viele grundsätzliche Probleme. Wenn mir dieser Code zur Überprüfung vorgelegt würde, würde ich Folgendes sagen:

Angenommen, Sie wollten zwei Tiefenrecherchen dieser Datenstruktur gleichzeitig durchführen. Entweder weil Sie dies in mehreren Threads durchgeführt 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 ausführt. Was geschieht? Sie stören sich, weil beide versuchen, die Felder "State" und "VisitNumber" zu ändern. Es ist eine wirklich schlechte Idee, einen "sauberen" Vorgang zu haben, wie das Durchsuchen Ihrer Datenstruktur tatsächlich "schmutzig" macht.

Auf diese Weise können Sie auch permanente unveränderliche Daten verwenden, um redundante Teile Ihres Diagramms darzustellen.

Ich stelle auch fest, dass Sie den Code weglassen, der bereinigt. Wann wird "State" immer auf seinen ursprünglichen Wert zurückgesetzt? Was wäre, wenn Sie eine zweite DFS erstellt hätten? Es würde sofort fehlschlagen, da die Wurzel bereits besucht ist.

Aus all diesen Gründen ist es eine bessere Wahl, den Status "besuchte" in seinem eigenen Objekt und nicht in jedem Scheitelpunkt zu behalten.

Warum sind alle Zustandsobjekte private Variablen einer Klasse? Dies ist ein einfacher Algorithmus. Es ist nicht nötig, eine ganze Klasse dafür zu bauen. Ein Algorithmus für die Tiefensuche sollte den Graphen für die Suche als formalen Parameter und nicht als Objektstatus verwenden, und er sollte seinen eigenen lokalen Status in lokalen Variablen und nicht in Feldern beibehalten.

Als nächstes ist die Abstraktion des Graphen ... na ja, es ist keine Abstraktion. Es gibt zwei Listen, eine von Scheitelpunkten und eine von Kanten. Woher wissen wir, dass diese beiden Listen sogar konsistent sind? Angenommen, es gibt Scheitelpunkte, die sich nicht in der Scheitelpunktliste befinden, sich aber in der Kantenliste befinden. Wie verhindern Sie das? Was Sie wollen, ist eine Graph-Abstraktion. Lassen Sie die Implementierung der Diagrammabstraktion sich darum kümmern, wie Kanten dargestellt und Nachbarn gesucht werden.

Als Nächstes ist Ihre Verwendung von ForEach sowohl legal als auch üblich, aber mein Kopf tut weh. Es ist schwer, Ihren Code und die Gründe dafür mit allen Lambdas zu lesen. Wir haben eine absolut gute "foreach" -Anweisung. Benutze es.

Als Nächstes mutieren Sie eine "übergeordnete" Eigenschaft, aber es ist überhaupt nicht klar, wozu diese Eigenschaft dient oder warum sie während einer Durchquerung mutiert wird. Scheitelpunkte in einem beliebigen Graphen haben keine "Eltern", es sei denn, der Graph ist ein Baum. Wenn es sich bei dem Graphen um einen Baum handelt, ist es nicht erforderlich, den Status "besucht" zu verfolgen. Es gibt keine Schleifen in einem Baum. Was geht hier vor sich? Dieser Code ist nur bizarr und es ist nicht notwendig, eine DFS durchzuführen.

Als Nächstes ist Ihre Hilfsmethode GetConnectedVertices eine Lüge. Es werden keine verbundenen Scheitelpunkte, es werden nicht bereits besuchte Scheitelpunkte verbunden. Methoden, deren Namen lügen, sind sehr verwirrend.

Schließlich behauptet dies, dass es sich um eine Tiefensuche handelt, aber sucht nicht nach irgendetwas! Wo wird das Ding gesucht? Wo wird das Ergebnis zurückgegeben? Dies ist keine Suche, sondern eine Durchquerung.

Von vorn anfangen. Was willst du? Eine tiefste Durchquerung eines Graphen bei einem Startscheitelpunkt . Dann das umsetzen. Beginnen Sie damit, zu definieren, was Sie durchqueren. Ein Graph. Welchen Service benötigen Sie aus einer Grafik? Eine Möglichkeit, die Menge benachbarter Scheitelpunkte abzurufen:

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

Was ist deine Methode zurück? Eine Folge von Scheitelpunkten in der Tiefe. Was braucht es? Ein Startscheitelpunkt. OK:

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

Wir haben jetzt eine triviale Implementierung der Tiefensuche; 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 eine Durchquerung durchgeführt wird, ohne den Zustand des Graphen 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 Zustandsveränderung. Kein Herumspielen mit Edge-Listen. Keine schlecht benannten Hilfsfunktionen. Und der Code macht tatsächlich das, was er sagt: Er durchquert ein Diagramm. 

Wir bekommen auch die Vorteile von Iteratorblöcken; Wenn dies für eine Suche nach DF verwendet wird, wird die Iteration abgebrochen, wenn die Suchkriterien erfüllt sind. Wir müssen keine vollständige Durchquerung durchführen, wenn wir das Ergebnis früh finden.

52
Eric Lippert

Ich habe den Code von @ Eric für die DFS-Durchquerung für jede T verallgemeinert, damit die Dinge für jeden Typ funktionieren, der Kinder hat.

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();
        visited.Add(current);
        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);
        }
    }
}

Verwendungsbeispiel:

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

Das Problem liegt in der Reihenfolge, in der Sie die Elemente durchsuchen. Ihr for each in StartSearch garantiert keine Elementreihenfolge. Sie haben auch keine FindAll in der 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 OrderBy() hinzufügen, um die gewünschte Reihenfolge sicherzustellen.

1
Adrian Carneiro

Dies ist meine Implementierung, der Stack ist gut genug. Eine Umkehrung 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;
    }
0
Lepton

Elemente werden in umgekehrter Reihenfolge vom Stapel abgelegt, so wie sie darauf geschoben werden:

stach.Push () ergibt: 1 2 3 4 5

stack.pop () ergibt: 5 4 3 2 1 (also: von rechts nach links)

0
Flawless

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;
    }
0
Evan Machusak