时间戳

首页 > 解决方案 > 图形的深度优先搜索无法正常工作

c# - 图形的深度优先搜索无法正常工作

问题描述

我正在尝试进行深度优先搜索的 C# 实现。为了方便访问，我有一个Dictionary<int, List<int>>存储顶点和边。

字典值是：

Vertex | Edges List
--------------------
0      | {1}
--------------------
1      |  {2}
--------------------
2      | {0} 
--------------------

static Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();

public class Graph
    {
        public int Vertex;
        public List<int> Edges;

        public Graph(int V, List<int> E)
        {
            Vertex = V;
            Edges = E;
            dict.Add(V, E);
        }

public void DFS(Graph g)
{
     Stack<int> stk = new Stack<int>();
     int[] visited = new int[4];

     stk.Push(g.Vertex);
     visited[0] = g.Vertex;
     int i = 1;
     while (stk.Count > 0)
     {
         foreach (var item in dict[stk.Peek()])
         {
             if (!visited.Contains(item))
             {
                 visited[i] = item;
                 stk.Push(item);
                 i++;
             }
         }
         Console.WriteLine(stk.Peek());
         stk.Pop();
    }
}

我在深度优先搜索中只得到 0 和 1。我知道有不同的方法可以做到这一点，但我相信我的方法也是其中一种方法，我需要帮助修复这段代码。

标签： c#algorithmgraph-algorithmdepth-first-search

解决方案

我想向您推荐一个现有的、简单且有用的深度优先遍历实现：https ://github.com/morelinq/MoreLINQ/blob/d45294865625aae1bf972f331a6737961473d136/MoreLinq/Traverse.cs#L87

有趣的部分：

public static IEnumerable<T> TraverseDepthFirst<T>(T root, Func<T, IEnumerable<T>> childrenSelector)
{
    if (childrenSelector == null) throw new ArgumentNullException(nameof(childrenSelector));

    return _(); IEnumerable<T> _()
    {
        var stack = new Stack<T>();
        stack.Push(root);

        while (stack.Count != 0)
        {
            var current = stack.Pop();
            yield return current;
            // because a stack pops the elements out in LIFO order, we need to push them in reverse
            // if we want to traverse the returned list in the same order as was returned to us
            foreach (var child in childrenSelector(current).Reverse())
                stack.Push(child);
        }
    }
}

通过将实现镜像到您的代码中，我们将得到以下内容：

public void DFS(Graph g)
{
     Stack<int> stk = new Stack<int>();
     HashSet<int> visited = new HashSet<int>();

     stk.Push(g.Vertex);
     visited.Add(g.Vertex);
     while (stk.Count > 0)
     {
         int current = stk.Pop();
         Console.WriteLine(current);
         foreach (var item in dict[current])
         {
             if (visited.Add(item))
             {
                 // Add returns true if the element wasn't in the set already
                 stk.Push(item);
             }
         }
    }
}

我已经删除了i变量，因为我们现在使用 HashSet 来跟踪访问过的顶点，并移动Console.WriteLine到stk.Pop()开头，因为这与我们在 MoreLinq 代码中看到的更接近，这也简化了代码。

您的方法是 Depth First Search，但您只是“访问”所有节点（我猜这Console.WriteLine是实际“查找/访问”操作的占位符）。在当前的形式中，它是遍历操作，对于搜索，您需要将顶点与您要查找的内容进行实际比较，并返回某种结果。

推荐阅读