核心步骤#

1
1. 从起点出发
2
2. 选择一个相邻且**未访问**节点，深入走下去
3
3. 直到无法继续前进（无路可走、到达目标、越界）
4
4. 立即回溯到上一个节点，尝试另一条未走的分支
5
5. 重复直到所有节点遍历完毕 / 找到目标

示例#

假设我们有一个无向图 G，如下图所示。

假设我们从起点1开始，按号数较小优先的方法使用深度优先搜索遍历该图。

1. 从起点1出发，首先访问1。
2. 和1相邻的节点有2、3和4，选择2。
3. 和2相邻的节点只有6，选择6。
4. 和6相邻的节点有5和7，选择5。
5. 由于5没有未访问的相邻节点，立即回溯到上一个节点6并继续访问6的另一个相邻节点7。
6. 访问7的相邻节点3。
7. 节点3没有未被访问的相邻节点，一直回溯到1，起点1还有一个相邻节点4，选择4。

由此，深度优先搜索的遍历顺序为：1 -> 2 -> 6 -> 5 -> 7 -> 3 -> 4。

算法实现#