logo标签列表

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

c#searchvertexdepthedges
32
我想创建一个深度优先搜索算法，我已经有了一些成功的尝试。
下面是我的代码（除了构造函数之外，请注意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;
}

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

这里是一个比较：我的算法和维基百科的算法相比，访问顶点的顺序不同： Comparison

似乎我的算法被翻转了，从右到左开始。

你知道是什么原因吗？（对我的实现有任何建议也将不胜感激）

编辑：我得到了答案，但仍想展示 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个回答
61
似乎我的文本从右到左开始了。您知道是什么原因吗？
正如其他人所指出的那样，您正在按照从左到右的顺序将要访问的节点推入堆栈中。这意味着它们被从右到左弹出，因为堆栈会反转顺序。堆栈是后进先出的。
您可以通过使GetConnectedVertices构建堆栈而不是列表来解决问题。这样，连接的顶点会反转两次，一次在返回的堆栈上，一次在实际堆栈上。
此外，对于我的实现，任何建议都将不胜感激。
我想这个实现可以工作，但它有很多基本问题。如果我需要审核该代码，我会说：
首先，假设您想同时对此数据结构进行两个深度优先搜索。无论是因为您在多个线程上执行它，还是因为您在内部循环中有一个嵌套循环，其中内部循环对不同于外部循环的元素执行DFS。会发生什么？他们会互相干扰，因为两者都试图改变“State”和“VisitNumber”字段。实际上，像搜索这样的操作应该是“干净”的操作，而不是让您的数据结构变得“脏”。
这样做还使您无法使用持久的不可变数据来表示图形的冗余部分。
另外，我注意到您省略了清理代码。何时将“State”设置回其原始值？如果您进行了第二个DFS会怎样？由于根已经被访问过，它将立即失败。
出于所有这些原因，更好的选择是将“visited”状态保留在自己的对象中，而不是每个顶点中。
接下来，为什么所有状态对象都是类的私有变量？这是一个简单的算法；没有必要为此构建整个类。深度优先搜索算法应将要搜索的图形作为正式参数，而不是作为对象状态，并且应根据需要在本地变量中维护其自己的本地状态，而不是字段。
接下来，图的抽象是……嗯，它不是抽象。它是两个列表，一个是顶点，一个是边。我们如何知道这两个列表甚至是一致的？假设有顶点不在顶点列表中，但在边列表中。你如何防止那个？您想要的是图形抽象。让图形抽象实现担心如何表示边缘和查找邻居。
最后，您对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);
    }
}

看到这段代码，你会发现它更加简洁易懂了。没有状态变化，没有涉及边缘列表的操作，也没有使用不合理的辅助函数。而且代码实际上做到了它所说的：遍历图。

我们还可以获得迭代器块的好处；即，如果有人将其用于深度优先搜索，则在满足搜索条件时就会停止迭代。如果提前找到结果，我们不必进行完整的遍历。

7
编译器不需要我的帮助，它知道数据类型。在这种情况下是否使用 "var" 的问题是人类是否需要帮助来理解它。你是一个人类；你真的需要看到“Stack<Vertex> stack = new Stack<Vertex>()”才能理解 stack 是一个顶点栈吗？我怀疑。冗余使代码更难读，而不是更容易，因此应该消除它。有关此主题的更多想法，请参见http://blogs.msdn.com/b/ericlippert/archive/2011/04/20/uses-and-misuses-of-implicit-typing.aspx。 - Eric Lippert
1
关于如何表示图形的问题，更多信息请参见http://en.wikipedia.org/wiki/Graph_(data_structure) -- 您建议使用“邻接表”方法来处理稀疏图形。而对于密集图形，“邻接矩阵”方法更为高效。 - Eric Lippert
2
@Atlas2k：你能问一个更具体的问题吗？这行代码的意思是“获取我尚未访问的邻居”。我们通过拥有一组已访问节点来表示这一点，然后获取所有尚未在已访问节点集中的邻居。你是否想知道为什么我们不想访问已经访问过的节点？因为问题是“按深度优先顺序访问每个节点”。 - Eric Lippert
2
@Atlas2k：您想要搜索的关键词是“lambda表达式”和“LINQ”。 - Eric Lippert
2
@ziezi，你的问题很容易自己回答。创建一个树形图并运行算法。它遍历节点的顺序是什么？ - Eric Lippert
显示剩余8条评论
6

我改进了@Eric的深度优先遍历代码，适用于任何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);
我认为这可能包含一个错误，正如我在@EricLippert的回答中提到的评论中所述。 - Matt Smith
1
问题在于搜索元素的顺序。你在StartSearch中使用的for each不能保证元素的顺序。同样，GetConnectedVertices方法中的FindAll也不能保证元素的顺序。让我们看一下这行代码： 

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

你应该添加一个 OrderBy() 来确保所需的顺序。
通过使用Reverse()函数来反转列表的顺序似乎解决了问题。感谢您的答案，让我朝着正确的方向前进。 - Dumpen
1
@Dumpen：你可以比使用Reverse更有效率地完成它。建立另一个栈！这样它就会自动按“反向”枚举。 - Eric Lippert
哦，这很聪明。你的意思是像这样吗？edges.FindAll(edge => edge.VertexSource == vertex && edge.VertexTarget.State == State.Unvisited). ForEach(edge => connectingVertices.Push(edge.VertexTarget));（抱歉，我好像无法正确格式化代码） - Dumpen
0

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

你可能会喜欢这个：

        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;
    }
谢谢。我一定会研究这个，但是目前我似乎已经在脑海中有足够的当前脚本了 :) - Dumpen
递归并不总是一个好主意，我会小心使用这个解决方案。 - vvondra
0

栈中的元素弹出顺序与它们被推入的顺序相反：

调用stack.push() 的结果为：1 2 3 4 5

调用stack.pop() 的结果为：5 4 3 2 1（即从右到左）

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接