使用List和Stack实现深度优先搜索到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"字段.这应该是一个"干净"的操作,如搜索实际上使您的数据结构"脏",这是一个非常糟糕的主意.

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

另外,我注意到你省略了清理的代码."状态"什么时候回到原来的价值？如果你做了第二次 DFS怎么办？它会立即失败,因为已经访问了root.

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

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

接下来,图的抽象是......好吧,它不是抽象.这是两个列表,一个是顶点,另一个是边.我们怎么知道这两个列表是否一致？假设有些顶点不在顶点列表中但位于边缘列表中.你怎么防止这种情况？你想要的是图形抽象.让图形抽象实现担心如何表示边缘并找到邻居.

接下来,您对ForEach的使用既合法又常见,但它让我头疼.很难用所有的lambdas读取你的代码和理由.我们有一个非常好的"foreach"声明.用它.

接下来,您正在改变"父"属性,但它根本不清楚这个属性是什么或为什么它在遍历期间被突变.任意图中的顶点没有"父",除非图是树,如果图是树,则不需要跟踪"访问"状态; 树中没有循环.这里发生了什么？这段代码很奇怪,没有必要执行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搜索,则在满足搜索条件时放弃迭代.如果我们尽早找到结果,我们不必进行完整的遍历.

Answer 2

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

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