使用列表和堆栈在 C# 中实现深度优先搜索

Question

我想创建一个深度优先搜索，我已经在其中取得了一些成功。

这是到目前为止我的代码（除了我的构造函数，请注意 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;
}

Answer 1

我的好像是转过来了，是从右到左开始的。你知道是什么原因造成的吗？

正如其他人所指出的，您将按从左到右的顺序推送堆栈上的下一个要访问的节点。这意味着它们会从右到左弹出，因为堆栈颠倒了顺序。堆栈是后进先出的。

您可以通过使 GetConnectedVertices 构建堆栈而不是列表来解决此问题。这样，连接的顶点就会反转两次，一次是当它们进入返回的堆栈时，一次是当它们进入真实的堆栈时。

此外，如果对我的实施有任何建议，我们将不胜感激

我想，该实现是有效的，但它有很多基本问题。如果有人向我提供该代码供审查，我会这么说：

首先，假设您想同时对此数据结构进行两次深度优先搜索。要么是因为您在多个线程上执行此操作，要么因为您有一个嵌套循环，其中内循环对与外循环不同的元素执行 DFS。会发生什么？它们相互干扰，因为两者都试图改变“State”和“VisitNumber”字段。像搜索这样应该是“干净”的操作实际上会让你的数据结构变得“脏”，这是一个非常糟糕的主意。

这样做还会使您无法使用持久不可变数据来表示图表的冗余部分。

另外，我注意到您省略了清理代码。 “State”什么时候会恢复到原来的值？如果您进行第二次 DFS 会怎样？由于根已经被访问过，它会立即失败。

出于所有这些原因，更好的选择是将“访问”状态保留在其自己的对象中，而不是保留在每个顶点中。

接下来，为什么所有的状态对象都是类的私有变量呢？这是一个简单的算法；无需为其构建整个类。深度优先搜索算法应该将要搜索的图作为形式参数，而不是对象状态，并且应该根据需要在局部变量而不是字段中维护自己的局部状态。

接下来，图的抽象是……好吧，它不是抽象。它有两个列表，一个是顶点，另一个是边。我们怎么知道这两个列表是一致的？假设存在不在顶点列表中但在边列表中的顶点。你如何防止这种情况发生？你想要的是图形抽象。让图抽象实现担心如何表示边并查找邻居。

接下来，您对 ForEach 的使用既合法又常见，但这让我很头疼。使用所有 lambda 表达式很难阅读代码并对其进行推理。我们有一个非常好的“foreach”语句。使用它。

接下来，您要改变“父”属性，但根本不清楚该属性的用途或为什么它在遍历期间被改变。任意图中的顶点没有“父节点”，除非该图是一棵树，并且如果该图是一棵树，则无需跟踪“已访问”状态；树中没有循环。这是怎么回事？这段代码很奇怪，而且没有必要执行DFS。

接下来，名为 GetConnectedVertices 的辅助方法是一个谎言。它没有连接顶点，而是连接尚未访问的顶点。名称错误的方法非常令人困惑。

最后，这声称是深度优先搜索，但它不搜索任何东西！正在搜索的东西在哪里？返回的结果在哪里？这根本不是搜索，而是遍历。

重新开始。你想要什么？ 给定起始顶点的图的深度优先遍历。然后实施它。首先定义您要遍历的内容。一张图表。您需要图表提供什么服务？获取相邻顶点集的一种方法：

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

您的方法返回什么？按深度优先顺序排列的顶点序列。需要什么？起始顶点。 OK：

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 搜索，那么当满足搜索条件时，迭代就会被放弃。如果我们尽早找到结果，就不必进行完整的遍历。

Answer 2

我概括了 @Eric 的任何 T 的 DFS 遍历代码，使之适用于任何有子项的类型 - 我想我会分享：

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

Answer 3

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

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

您应该添加一个 OrderBy() 以确保所需的顺序。

Answer 4

项目将以与压入堆栈相反的顺序从堆栈中弹出：

stach.push() 结果为： 1 2 3 4 5

stack.pop() 结果为： 5 4 3 2 1 （所以：从右开始向左）

Answer 5

你可能会喜欢这个：

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

Answer 6

这是我的实现，一堆就足够了。在 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;
    }