一、概述
图是计算机科学中的一类非常重要的数据结构，用于描述物体间的关系。在图中，节点（vertex）代表物体，边（edge）则代表物体间的关系。通过遍历图，我们可以对图中的节点进行访问，同时也可以找出图中节点之间的关系。
深度优先遍历是图遍历中重要的一种方法，它类似于二叉树的前序遍历，按照深度优先的方式访问图中的节点。具体而言，深度优先遍历会首先访问某个节点，接着访问该节点的邻居节点，并进一步访问邻居的邻居……直到访问到所有相关的节点。
本文主要介绍如何实现图的深度优先遍历，以及为什么它类似于二叉树。
二、图的深度优先遍历
在实现图的深度优先遍历时，我们需要考虑如何遍历每个节点，并标记哪些节点已经被遍历过。
下面是一个示例图，展示了深度优先遍历中的遍历顺序：
1 - 2 - 3
| | |
4 - 5 - 6
上图中，我们从节点1开始遍历，并首先访问它的邻居节点2。接着，我们访问节点2的邻居节点3，再访问节点3的邻居节点6……直到访问了所有相关的节点。
下面给出实现图的深度优先遍历的代码示例：
// 图的邻接表表示法
class Graph {
constructor() {
// 存储图的节点
this.vertices = [];
// 存储图的边
this.edges = new Map();
}
// 添加节点
addVertex(v) {
this.vertices.push(v);
this.edges.set(v, []);
}
// 添加边
addEdge(v, w) {
this.edges.get(v).push(w);
this.edges.get(w).push(v);
}
// 深度优先遍历
dfs(startingNode) {
const visited = new Set();
this._dfs(startingNode, visited);
}
_dfs(vertex, visited) {
visited.add(vertex);
console.log(vertex);
const neighbors = this.edges.get(vertex);
for (let i = 0; i < neighbors.length; i++) {
const neighbor = neighbors[i];
if (!visited.has(neighbor)) {
this._dfs(neighbor, visited);
}
}
}
}
三、图的深度优先遍历类似于二叉树的前序遍历
虽然图和二叉树是两种不同的数据结构，但它们之间的遍历方式非常相似。图的深度优先遍历类似于二叉树的前序遍历，都是首先访问本节点，接着访问左子节点（或者邻居节点），最后访问右子节点（或者邻居节点）。下面是一个对比图和二叉树前序遍历的示意图：
图的深度优先遍历： 二叉树的前序遍历：
1 A
/ \ / \
2 4 B D
/ \ \ / \ \
3 5 6 C E F
/ \ / \
G H I J
从上面的示意图中可以看出，图的深度优先遍历和二叉树的前序遍历本质上是相同的遍历方式。唯一的区别在于，图没有一个指定的根节点，而是从任一节点开始遍历。
下面给出实现图的深度优先遍历类似于二叉树前序遍历的代码示例：
class Graph {
// ...
// 深度优先遍历类似于二叉树前序遍历
dfs(node) {
const visited = new Set();
this._dfs(node, visited);
}
_dfs(node, visited) {
visited.add(node);
console.log(node);
const neighbors = this.edges.get(node);
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
this._dfs(neighbor, visited);
}
}
}
}
四、图的深度优先遍历与回溯
在实现图的深度优先遍历时，我们需要考虑如何在访问之后回到原来的节点。相比于二叉树的遍历，图的遍历涉及到多个路径，因此需要更加小心地考虑回溯的问题。
在深度优先遍历过程中，我们使用递归函数来遍历每个节点。如果我们走到一个死路，即当前节点没有相邻节点可访问，那么我们需要回到之前的节点（回溯），查找还有没有相邻节点可访问。如果回到原来的节点后，还有未访问的相邻节点，那么我们将继续访问，直到访问完所有相关的节点。
下面给出实现遍历时的回溯代码示例：
class Graph {
// ...
// 深度优先遍历
dfs(startingNode) {
const visited = new Set();
this._dfs(startingNode, visited);
}
_dfs(node, visited) {
visited.add(node);
console.log(node);
const neighbors = this.edges.get(node);
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
this._dfs(neighbor, visited);
}
}
}
}
五、图的深度优先遍历与栈
在上面的示例代码中，我们使用递归实现图的深度优先遍历。但递归调用可能会导致栈溢出的问题，特别是在遍历大型图时，很容易出现栈溢出错误。因此，我们可以使用栈（stack）来实现深度优先遍历，而不是使用递归函数。
在使用栈实现深度优先遍历时，我们需要考虑如何在遍历完一个节点之后，回溯到它的前一个节点，并继续遍历。因此，我们需要维护一个栈，保存已经访问过的节点。同时，我们还需要维护一个表，记录每个节点是否已经被访问过。
下面给出使用栈实现遍历的代码示例：
class Graph {
// ...
iter_dfs(startingNode) {
const visited = new Set();
const stack = [];
stack.push(startingNode);
while (stack.length !== 0) {
const node = stack.pop();
if (!visited.has(node)) {
visited.add(node);
console.log(node);
const neighbors = this.edges.get(node);
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
}
}
六、总结
对于图的深度优先遍历类似于二叉树的前序遍历，我们需要遍历每个节点，并标记哪些节点已经被遍历过。在实现遍历时，我们需要考虑如何回溯到原来的节点，以及使用栈来替代递归实现深度优先遍历。
图的深度优先遍历类似于二叉树的前序遍历，但需要注意的是，图的遍历涉及到多个路径，因此需要更加小心地考虑回溯的问题。
