邻接表无向图的深度优先遍历

如题，在“图基础-创造用于测试的简单图”文章提到的邻接表无向图代码的基础上，添加了深度优先遍历方法。

代码如下：

//0号节点开始，深度优先遍历图
        //思路：把0号节点入栈，从它开始，开始遍历之旅
        public void Dfs()
        {
            //创造遍历需要用到的全局工具
            //栈，保存需要遍历节点的相连节点，实现DFS需要的顺序
            Stack<int> stack = new();
            //标记数组，保存每个点是否已被打印。防止无限输出。
            bool[] flags = new bool[nodes.Length];
            stack.Push(0);
            //开始DFS
            Dfs(stack, flags);
        }
        
        //思路：从栈里取点
        //没打过，就打出来，标记为“打印过”，再把它的相连点入栈。
        //打过，就算了。
        public void Dfs(Stack<int> s, bool[] b)
        {
            int x;
            //栈不空，就取里面的元素出来
            while (s.Count > 0)
            {
                x = s.Pop();
                //如果没打印过
                if (b[x] == false)
                {
                    //打出来
                    Console.WriteLine(nodes[x].v + " ");
                    //标记成“打印过”
                    b[x] = true;
                    //所有相连节点入栈
                    //（由于此处不计顺序，故可能有多种结果）
                    foreach (var item in nodes[x].next)
                    {
                        s.Push(item);
                    }
                }
            }
        }

其中，“栈”是深度优先遍历算法中，保证输出顺序正确的关键。

测试用主程序：

static void Main(string[] args)
        {
            MyTable g1 = new();
            g1.testShow();
            g1.Dfs();
        }

运行结果：

节点v0,边：1  2  4
节点v1,边：0  2
节点v2,边：0  1  4
节点v3,边：4
节点v4,边：0  2  3
v0
v4
v3
v2
v1

经验证，正确。

邻接表无向图的深度优先遍历

相关推荐