邻接表深度优先遍历和广度优先遍历的例子

假设我们有以下无向图：

A -- B -- C
|    |    |
D -- E -- F

邻接表表示为：

A: B, D
B: A, C, E, D
C: B, F
D: A, E
E: B, C, D, F
F: C, E

那么，深度优先遍历的顺序为：A -> B -> C -> F -> E -> D

广度优先遍历的顺序为：A -> B -> D -> C -> E -> F

深度优先遍历的过程：

1. 从节点 A 开始遍历，将其标记为已访问。
2. 遍历邻居节点 B，因为 B 还没有被访问过，所以以 B 为起点开始递归遍历。
3. 在递归遍历 B 的邻居节点时，先访问 D，再返回到 B，再访问 C。
4. 在递归遍历 C 的邻居节点时，发现 F 还没有被访问过，以 F 为起点递归遍历。
5. 在递归遍历 F 的邻居节点时，发现 E 还没有被访问过，以 E 为起点递归遍历。
6. 在递归遍历 E 的邻居节点时，先访问 D，再返回到 E，再访问 C。
7. 因为图中所有节点都已经被访问过，遍历结束。

广度优先遍历的过程：

1. 从节点 A 开始遍历，将其标记为已访问，并把它加入到队列中。
2. 从队列中取出 A，遍历其邻居节点 B 和 D，并将它们加入到队列中。
3. 从队列中取出 B，遍历其邻居节点 C 和 E，并将它们加入到队列中。
4. 从队列中取出 D，遍历其邻居节点 E，并将它加入到队列中。
5. 从队列中取出 C，遍历其邻居节点 F，并将它加入到队列中。
6. 从队列中取出 E，发现它的邻居节点 C 还没有被访问过，将其加入到队列中。
7. 从队列中取出 F，发现它的邻居节点 E 还没有被访问过，将其加入到队列中。
8. 因为图中所有节点都已经被访问过，遍历结束。