深度优先搜索: 探索图结构的括号化旅程

在解决图相关问题时，深度优先搜索（DFS）是一种非常有用的算法。DFS 通过递归或使用栈的方式遍历图的节点，尽可能深地搜索每一个分支，然后回溯以搜索其他未访问的节点。本文将详细讨论如何通过深度优先搜索（DFS）生成图的括号化结构，并使用伪代码和C代码来具体实现这一算法。

图的括号化结构

图的括号化结构是一种表示图遍历顺序的方式，使用括号来标识每次递归调用。对于无向图来说，括号化结构可以很好地展示DFS的遍历过程，其中每个节点和其子节点的访问顺序被包含在一对括号内。

示例图

假设图 22-4 是一个无向图，具有如下边：

• (0, 1)
• (0, 2)
• (1, 2)
• (1, 3)
• (3, 4)

该图有 5 个节点，编号从 0 到 4。

深度优先搜索的伪代码

首先，我们给出DFS生成括号化结构的伪代码：