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

Question

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

Dict 值是:

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。我知道有不同的方法可以做到这一点，但我相信我的方法也是其中一种方法，我需要帮助修复这段代码。

Answer 1

据我了解，您的代码执行以下操作:
1. 将第一个顶点压入堆栈
2. 偷看它，并搜索不在堆栈中的第一条边
3. 压栈
4. 偷看
5. 从栈中弹出。通过这一步，第一个顶点(在本例中为顶点 0)到达堆栈的顶部，然后您的代码转到 2.point。
由于一步无法从顶点 0 到达顶点 2，因此您的算法停止。