使用列表和堆栈在 C# 中实现深度优先搜索 [英] Implementing Depth First Search into C# using List and Stack

问题描述

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

I want to create a depth first search which I have been somewhat successful in.

到目前为止，这是我的代码(除了我的构造函数，注意 Vertex 和 Edge 类只包含属性，这里没有什么重要的内容):

Here is my code so far (Except my constructor, note the Vertex and Edge classes only contain properties, nothing important to post here):

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

它的工作方式是访问所有顶点，但顺序不正确.

Its working in the way that all vertices get visited, but not in the right order.

以下是我的访问方式与维基百科的比较:

Here is a comparison of how mine gets visited compared to wikipedia:

我的好像是掉头了，从右到左开始.

Its seems mine is turned around and is beginning from right to left.

你知道是什么原因造成的吗?(对于我的实施的任何建议也将不胜感激)

Do you know what causes it? (Also any advice on my implementation would be greatly appreciated)

我得到了答案，但仍想显示 GetConnectedVertices 方法的最终结果:

I got my answer, but still wanted to show the end result for the GetConnectedVertices method:

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

推荐答案

我的好像是掉头了，是从右到左开始的.你知道是什么原因造成的吗?

It seems mine is turned around and is beginning from right to left. Do you know what causes it?

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

As others have noted, you are pushing the nodes-to-visit-next on the stack in order from left to right. That means they get popped off right-to-left, since a stack reverses the order. Stacks are last-in-first-out.

您可以通过让 GetConnectedVertices 构建堆栈而不是列表来解决问题.这样，连接的顶点被反转两次，一次是在它们进入返回的堆栈时，一次是在它们进入真正的堆栈时.

You can fix the problem by making GetConnectedVertices build a stack, not a list. That way the connected vertices are reversed twice, once when they go on the returned stack and once when they go on the real stack.

对于我的实施的任何建议也将不胜感激

Also any advice on my implementation would be greatly appreciated

我想这个实现是有效的，但它有很多基本问题.如果向我展示该代码以供审核，我会说:

The implementation works, I suppose, but it has a great many fundamental problems. If I were presented that code for review, here's what I'd say:

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

First off, suppose you wanted to do two depth-first searches of this data structure at the same time. Either because you were doing it on multiple threads, or because you have a nested loop in which the inner loop does a DFS for a different element than the outer loop. What happens? They interfere with each other because both try to mutate the "State" and "VisitNumber" fields. It is a really bad idea to have what should be a "clean" operation like searching actually make your data structure "dirty".

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

Doing so also makes it impossible for you to use persistent immutable data to represent redundant portions of your graph.

另外，我注意到您省略了清理代码.State"什么时候恢复到原来的值?如果你做了一个第二 DFS 会怎样?由于根已经被访问过，它会立即失败.

Also, I notice that you omit the code that cleans up. When is "State" ever set back to its original value? What if you did a second DFS? It would immediately fail since the root is already visited.

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

A better choice for all these reasons is to keep the "visited" state in its own object, not in each vertex.

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

Next, why are all the state objects private variables of a class? This is a simple algorithm; there's no need to build an entire class for it. A depth first search algorithm should take the graph to search as a formal parameter, not as object state, and it should maintain its own local state as necessary in local variables, not fields.

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

Next, the abstraction of the graph is... well, its not an abstraction. It's two lists, one of vertices and one of edges. How do we know that those two lists are even consistent? Suppose there are vertices that are not in the vertex list but are on the edge list. How do you prevent that? What you want is a graph abstraction. Let the graph abstraction implementation worry about how to represent edges and find neighbours.

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

Next, your use of ForEach is both legal and common, but it makes my head hurt. It is hard to read your code and reason about it with all the lambdas. We have a perfectly good "foreach" statement. Use it.

接下来，您正在改变父"属性，但完全不清楚此属性的用途或为什么在遍历过程中会发生突变.任意图中的顶点没有父节点"，除非该图是一棵树，并且如果该图是一棵树，则无需跟踪已访问"状态；树中没有循环.这里发生了什么?这段代码很奇怪，没必要做DFS.

Next, you are mutating a "parent" property but it is not at all clear what this property is for or why it is being mutated during a traversal. Vertices in an arbitrary graph do not have "parents" unless the graph is a tree, and if the graph is a tree then there is no need to keep track of the "visited" state; there are no loops in a tree. What is going on here? This code is just bizarre, and it is not necessary to perform a DFS.

接下来，您的名为 GetConnectedVertices 的辅助方法是个谎言.它没有连接顶点，它连接了尚未访问的顶点.名称谎言的方法非常混乱.

Next, your helper method named GetConnectedVertices is a lie. It does not get connected vertices, it gets connected not-already-visited vertices. Methods whose names lie are very confusing.

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

Finally, this claims to be a depth first search but it doesn't search for anything! Where is the thing being searched for? Where is the result returned? This isn't a search at all, it's a traversal.

重新开始.你想要什么?给定起始顶点的图的深度优先遍历.然后执行那个.首先定义您要遍历的内容.一个图表.从图表中您需要什么服务?一种获取相邻顶点集的方法:

Start over. What do you want? A depth-first traversal of a graph given a starting vertex. Then implement that. Start by defining what you are traversing. A graph. What service do you need from a graph? A way of getting the set of neighbouring vertices:

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

你的方法返回什么?深度优先顺序的顶点序列.需要做些什么?一个起始顶点.好的:

What is your method returning? A sequence of Vertices in depth-first order. What does it take? A starting vertex. OK:

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

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

We now have a trivial implementation of depth first search; you can now use the Where clause:

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

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

OK, so how are we going to implement that method so it does a traversal without wrecking the graph's state? Maintain your own external state:

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

看看它更简洁、更短?没有状态突变.不要乱用边缘列表.没有名字不好的辅助函数.并且代码实际上做了它所说的:遍历一个图.

See how much cleaner and shorter that is? No mutation of state. No mucking around with edge lists. No badly-named helper functions. And the code actually does what it says it does: traverses a graph.

我们也得到了迭代器块的好处；即，如果有人将其用于 DF 搜索，则在满足搜索条件时放弃迭代.如果我们早点找到结果，我们就不必进行完全遍历.

We also get the benefits of iterator blocks; namely, if someone is using this for a DF search, then the iteration is abandoned when the search criteria are met. We don't have to do a full traversal if we find the result early.

这篇关于使用列表和堆栈在 C# 中实现深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！