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

问题描述

我要创造，我已经有点成功的在深度优先搜索。

下面是我的code到目前为止（除了我的构造函数，注意顶点和边类仅包含属性，没什么重要的是要在这里发布）：

 专用堆叠式和LT;顶点＆GT; workerStack =新的堆栈＆LT;＆顶点GT;（）;
私人列表＆LT;＆顶点GT;顶点=新的List＆LT;＆顶点GT;（）;
私人列表＆LT;边及GT;边=新的List＆LT;边及GT;（）;私人诠释numberOfVertices;
私人诠释numberOfClosedVertices;
私人INT visitNumber = 1;私人无效开始搜索（）
{
    //确保访问所有顶点
    而（numberOfClosedVertices＆所述; numberOfVertices＆放大器;＆放大器; workerStack.Count大于0）
    {
        //获取栈顶元素并参观了其标记
        顶点workingVertex = workerStack.Pop（）;
        workingVertex.State = State.Visited;        workingVertex.VisitNumber = visitNumber;
        visitNumber ++;        numberOfClosedVertices ++;        //获取连接到工作顶点的所有边缘
        的foreach（顶点顶点GetConnectedVertices（workingVertex））
        {
            vertex.Parent = workingVertex;
            workerStack.Push（顶点）;
        }
    }
}私人列表＆LT;＆顶点GT; GetConnectedVertices（顶点顶点）
{
    清单＆LT;＆顶点GT;顶点=新的List＆LT;＆顶点GT;（）;    //获取连接到顶点的所有顶点和未访问过的是，然后将它们添加到列表中的顶点
    edges.FindAll（边缘=＆GT; edge.VertexSource ==顶点和放大器;＆安培; edge.VertexTarget.State == State.Unvisited）.ForEach（边=＆GT; vertices.Add（edge.VertexTarget））;    回到顶点;
}
 

及其在所有顶点获得访问，但不能以正确的顺序。顺便工作

下面是矿山如何被走访相比，维基百科的比较：

它似乎矿转头是从右到左开始。

你知道是什么原因造成的？ （同样在我的实现任何建议将不胜AP preciated）

感谢

编辑：我有我的答案，但仍想以示对GetConnectedVertices方法的最终结果是：

 私人列表＆LT;＆顶点GT; GetConnectedVertices（顶点顶点）
{
    清单＆LT;＆顶点GT; connectingVertices =新的List＆LT;＆顶点GT;（）;    （从在边缘的边缘
     其中，edge.VertexSource ==顶点和放大器;＆安培; edge.VertexTarget.State == State.Unvisited
     选择边）。
     相反（）。
     了ToList（）。
     的ForEach（边缘=＆GT; connectingVertices.Add（edge.VertexTarget））;    返回connectingVertices;
}
 

解决方案

  

这似乎矿转头从右到左开始。你知道是什么原因造成的？

正如其他人指出，你正在推动节点到访问-下在栈上，以便从左到右。这意味着它们会弹出右到左，由于堆反转的顺序。栈是后进先出。

您可以通过GetConnectedVertices建立一个堆栈，而不是一个清单解决问题。这样连接的顶点反转的两次的，一旦当他们返回堆栈上，当他们去真正的堆栈一次。

  

另外我实施任何建议将不胜AP preciated

实施工作的，我想，但它有一个很大的许多基本问题。如果我是presented是code审查，这里就是我想要说什么：

首先，假设你想在同一时间做这个数据结构的两个深度优先搜索。无论是因为你做的多线程，或者因为你有一个嵌套的循环，其中内环做了DFS比外环不同的元素。发生了什么？他们互相干扰，因为这两种尝试变异的国家和VisitNumber领域。这是一个非常糟糕的主意，有什么应该是像搜索实际上使你的数据结构脏的一个干净的操作。

这样做也使得它不可能为你使用的永久不变的数据的重新present您的图形的冗余部分。

另外，我注意到，你忽略了code来清理。当国家曾经设置回其原始值？如果你做了的第二的DFS？这将立即失败，因为根已经访问了。

所有这些原因，更好的选择是保持在自己的对象访问的状态，而不是在每一个顶点。

其次，为什么所有的状态对象类的私有变量？这是一个简单的算法;有没有必要建立一个完整的类吧。深度优先搜索算法应采取图形搜索作为一个正式的参数，而不是对象状态，它应该是必要的局部变量，而不是域维护自己的本地状态。

接下来，图的抽象是......好吧，它不是一种抽象。它的两个列表，顶点之一和边缘之一。我们怎么知道，这两个名单是均匀一致？假设有顶点不在顶点列表中，但是在边缘列表上。你怎么prevent是什么？你想要的是一个图形抽象。让我们了解如何重新present边和邻居找到图形抽象实施担心。

接下来，您的foreach的使用是合法和普遍，但它使我的头很疼。这是很难与所有的lambda表达式来读取你的code和理由了。我们有一个非常好的的foreach语句。使用它。

接下来将变异父属性，但它并不清楚这是什么属性是为什么它被遍历过程中突变。在任意图的顶点没有父母，除非该图是一棵树，如果图是一棵树那么就没有必要跟踪访问的状态;有在树上没有环路。这里发生了什么？此code是刚刚离奇，并且没有必要执行DFS

接下来，你叫GetConnectedVertices辅助方法，是骗人的。它没有得到连接的顶点，它就会连接不-已经访问过的顶点。方法的名字说谎是非常混乱的。

最后，声称是一个深度优先搜索，但的它不会搜索任何东西！的哪里是要搜索的东西吗？哪里的结果返回？这不是一个搜索的话，那是一个穿越。

重新开始。你想要什么？ 给出起始顶点图的深度优先遍历。然后实现。通过定义你遍历什么时开始。的图表。你从图中需要什么样的服务？获得组相邻顶点的一种方式：

 接口IGRAPH
{
    IEnumerable的＆LT;＆顶点GT; GetNeighbours（顶点v）;
}
 

你有什么方法返回？顶点的深度优先序列。是什么时间？的起始顶点。 OK：

 静态类扩展
{
    公共静态的IEnumerable＆LT;＆顶点GT; DepthFirstTraversal（
        这IGRAPH图，
        顶点开始）
    {...}
}
 

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

  IGRAPH为MyGraph =什么;
顶点开始=什么;
顶点的结果= myGraph.DepthFirstTraversal（开始）
                       。凡（V =＆GT;的东西）
                       .FirstOrDefault（）;
 

好，那么我们如何让它遍历不破坏图形的状态，以实现该方法？维护自己的外部状态：

 公共静态的IEnumerable＆LT;＆顶点GT; DepthFirstTraversal（
    这IGRAPH图，
    顶点开始）
{
    VAR走访=新的HashSet＆LT;＆顶点GT;（）;
    VAR堆栈=新的堆栈＆LT;＆顶点GT;（）;    stack.Push（启动）;    而（stack.Count！= 0）
    {
        无功电流= stack.Pop（）;        如果（！visited.Add（电流））
            继续;        产量返回电流;        VAR邻居= graph.GetNeighbours（电流）
                              。凡（N =＆GT;！visited.Contains（正））;        //如果你不关心左到右的顺序，删除反
        的foreach（在neighbours.Reverse变种邻居（））
            stack.Push（邻居）;
    }
}
 

请参阅如何更清洁和更短的那是什么？国家没有突变。没有用边列表碴左右。无严重命名的辅助函数。而code实际上做什么它说，它的作用：横贯图。

我们还可以得到迭代器块的利益;即，如果有人用这个的DF搜索，那么迭代时搜索条件得到满足抛弃。我们没有做一个完整的遍历，如果我们及早发现的结果。

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

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)

Thanks

EDIT: 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.

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:

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.

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.

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.

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.

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) 
    { ... }
}

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.

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屋！