使用列表和堆栈对C＃进行深度优先搜索

|| 我想创建一个深度优先的搜索，该搜索已经取得了一定的成功。到目前为止，这是我的代码（除我的构造函数外，请注意Vertex和Edge类仅包含属性，在此处没有重要内容可发布）：

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

它以访问所有顶点的方式工作，但顺序不正确。与维基百科相比，这是我的访问方式的比较：它似乎是我的转身，并且是从右到左开始的。你知道是什么原因吗？（此外，对于我的实施方案，我们将不胜感激）编辑：我得到了答案，但仍想显示GetConnectedVertices方法的最终结果：

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

已邀请:

6 个回复

物崎巩

似乎我的转身从右到左开始。你知道是什么原因吗？正如其他人指出的那样，您是按从左到右的顺序将节点上的访问节点下推。这意味着它们会从右到左弹出，因为堆栈会颠倒顺序。堆栈是后进先出的。您可以通过使GetConnectedVertices生成堆栈而不是列表来解决此问题。这样，连接的顶点将反转两次，一次是在返回的堆栈上，一次是在实际堆栈上。此外，我的实施任何建议将不胜感激我想该实现有效，但是它有很多基本问题。如果我收到要检查的代码，这就是我要说的：首先，假设您想同时对该数据结构进行两次深度优先搜索。可能是因为您在多个线程上执行此操作，或者是因为您有一个嵌套循环，其中，内部循环为不同于外部循环的元素执行DFS。怎么了？它们彼此干扰，因为它们都试图突变\“ State \”和\“ VisitNumber \”字段。进行应为“干净”的操作（例如搜索实际上使您的数据结构为“脏”）是一个非常糟糕的主意。这样做还使您无法使用永久不变数据表示图形的冗余部分。另外，我注意到您省略了清理代码。 “状态”何时恢复为原始值？如果您做了第二个DFS怎么办？由于已经访问过根，因此它将立即失败。由于所有这些原因，更好的选择是将“已访问”状态保留在其自己的对象中，而不是在每个顶点中。接下来，为什么所有状态对象都是类的私有变量？这是一个简单的算法；无需为其构建整个类。深度优先搜索算法应将图搜索作为形式参数而不是对象状态，并且应根据需要在局部变量（而不是字段）中保持自己的局部状态。接下来，图的抽象是...好吧，它不是抽象。这是两个列表，一个是顶点，另一个是边。我们怎么知道这两个列表是一致的？假设有些顶点不在顶点列表中，但在边列表中。您如何预防呢？您想要的是图形抽象。让图抽象实现担心如何表示边并找到邻居。其次，您对ForEach的使用既合法又普遍，但这会让我头疼。很难用所有的lambda读取代码和原因。我们有一个非常好的“ foreach”语句。用它。接下来，您要对\“ parent \”属性进行变异，但根本不清楚该属性的作用或遍历过程中为何对其进行变异。除非该图是一棵树，否则任意图中的顶点都不会具有“父级”，并且如果该图是一棵树，则无需跟踪“已访问”状态。一棵树上没有循环。这里发生了什么？这段代码很奇怪，不需要执行DFS。接下来，名为GetConnectedVertices的帮助程序方法是一个谎言。它不会获得连接的顶点，而会获得尚未访问的顶点。名称说谎的方法非常令人困惑。最后，这声称是深度优先搜索，但它不搜索任何内容！在哪里寻找东西？结果返回哪里？这根本不是搜索，而是遍历。重来。你想要什么？给定起始顶点的图的深度优先遍历。然后实施。首先定义要遍历的内容。图。您需要从图表中获得什么服务？一种获取相邻顶点集的方法：

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

您返回的方法是什么？深度优先的一系列顶点。需要做些什么？起始顶点。好：

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

现在，我们有了一个深度优先搜索的简单实现；您现在可以使用Where子句：

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

好的，那么我们将如何实现该方法，以便在不破坏图形状态的情况下进行遍历？保持自己的外部状态：

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

看看那是多少更清洁和更短？状态无突变。不要与边缘列表混为一谈。没有名称不正确的助手功能。并且代码实际上按照其声明的方式运行：遍历图形。我们还获得了迭代器块的好处；也就是说，如果有人将其用于DF搜索，则在满足搜索条件时将放弃迭代。如果我们尽早发现结果，则不必进行完整遍历。

babsoft

我将@Eric的代码用于DFS遍历的任何any6进行通用化，以使其对具有子代的任何类型都有效-我想我愿意分享：

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

用法示例：

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

徘廷

问题出在搜索元素的顺序上。您在StartSearch中的for each不保证元素顺序。您也不会以GetConnectedVertices方法FindAll。让我们看一下这一行：

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

您应添加一个“ 14”以确保所需的顺序。

杭难插

物品将按相反的顺序从堆叠中弹出： stach.push（）结果为：1 2 3 4 5 stack.pop（）结果为：5 4 3 2 1（因此：从右到左）

屡倒雷图

您可能会喜欢：

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

抚驰

这是我的实现，一个堆栈就足够了。在foreach循环之前执行相反的操作。

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

要回复问题请先登录或注册

使用列表和堆栈对C＃进行深度优先搜索

6 个回复

发起人

vertex

edges

search

c#

depth

问题状态

使用列表和堆栈对C＃进行深度优先搜索

与内容相关的链接

6 个回复

发起人

vertex

edges

search

c#

depth

问题状态