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

邻接表是一种常用的图的表示方法，它使用链表来表示图中每个顶点的邻接点。邻接表的深度优先遍历和广度优先遍历可以通过递归和队列来实现。

邻接表的深度优先遍历（DFS）可以按照以下步骤进行：
1. 创建一个空的栈，用于存储待访问的顶点。
2. 选择一个起始顶点，并将其标记为已访问。
3. 将起始顶点入栈。
4. 当栈不为空时，执行以下操作：
- 弹出栈顶顶点，并将其输出。
- 遍历该顶点的邻接表，对于每个未访问的邻接点，将其标记为已访问，并将其入栈。
5. 重复步骤4，直到栈为空。

邻接表的广度优先遍历（BFS）可以按照以下步骤进行：
1. 创建一个空的队列，用于存储待访问的顶点。
2. 选择一个起始顶点，并将其标记为已访问。
3. 将起始顶点入队列。
4. 当队列不为空时，执行以下操作：
- 弹出队首顶点，并将其输出。
- 遍历该顶点的邻接表，对于每个未访问的邻接点，将其标记为已访问，并将其入队列。
5. 重复步骤4，直到队列为空。

相关问题

邻接表深度优先遍历和广度优先遍历的代码

以下是邻接表深度优先遍历和广度优先遍历的 Python 代码实现：

from collections import deque

# 定义邻接表
graph = {
    0: [1, 4],
    1: [0, 2, 3, 4],
    2: [1, 3],
    3: [1, 2, 4],
    4: [0, 1, 3]
}

# 深度优先遍历
def dfs(graph, start):
    visited = set()  # 用集合记录已经访问过的节点
    stack = [start]  # 用栈记录需要遍历的节点
    while stack:
        node = stack.pop()  # 取出栈顶节点
        if node not in visited:
            visited.add(node)  # 标记为已访问
            print(node, end=" ")
            # 将未访问过的相邻节点加入栈中
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

# 广度优先遍历
def bfs(graph, start):
    visited = set()  # 用集合记录已经访问过的节点
    queue = deque([start])  # 用队列记录需要遍历的节点
    while queue:
        node = queue.popleft()  # 取出队首节点
        if node not in visited:
            visited.add(node)  # 标记为已访问
            print(node, end=" ")
            # 将未访问过的相邻节点加入队列中
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 测试
dfs(graph, 0)  # 输出：0 1 2 3 4
print()
bfs(graph, 0)  # 输出：0 1 4 2 3

注意，以上代码中使用了集合和队列来记录已经访问过的节点和需要遍历的节点。在 Python 中，集合可以使用 set 类型来实现，队列可以使用 deque 类型来实现。

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

### 回答1：
假设我们有以下有向图：

1 -> 2 -> 4
|  / |  / |
v v  v v  v
3 -> 5 -> 6

邻接表表示为：

1: [2, 3]
2: [4, 5, 3]
3: [5]
4: []
5: [4, 6]
6: []

深度优先遍历的过程如下：

1. 从顶点1开始，将其标记为访问过，输出1
2. 遍历邻接表中与1相邻的未访问过的顶点，选择顶点2，将其标记为访问过，输出2
3. 遍历邻接表中与2相邻的未访问过的顶点，选择顶点4，将其标记为访问过，输出4
4. 遍历邻接表中与4相邻的未访问过的顶点，发现没有，回溯到2
5. 遍历邻接表中与2相邻的未访问过的顶点，选择顶点5，将其标记为访问过，输出5
6. 遍历邻接表中与5相邻的未访问过的顶点，选择顶点6，将其标记为访问过，输出6
7. 遍历邻接表中与6相邻的未访问过的顶点，发现没有，回溯到5
8. 遍历邻接表中与5相邻的未访问过的顶点，发现没有，回溯到2
9. 遍历邻接表中与2相邻的未访问过的顶点，选择顶点3，将其标记为访问过，输出3
10. 遍历邻接表中与3相邻的未访问过的顶点，选择顶点5，发现已经访问过，回溯到1
11. 遍历邻接表中与1相邻的未访问过的顶点，发现没有，遍历结束

深度优先遍历的输出结果为：1 -> 2 -> 4 -> 5 -> 6 -> 3

广度优先遍历的过程如下：

1. 从顶点1开始，将其标记为访问过，加入队列中
2. 队列中弹出顶点1，遍历邻接表中与1相邻的未访问过的顶点，选择顶点2，将其标记为访问过，加入队列中
3. 队列中弹出顶点2，遍历邻接表中与2相邻的未访问过的顶点，选择顶点4和5，将其标记为访问过，加入队列中
4. 队列中弹出顶点4，遍历邻接表中与4相邻的未访问过的顶点，发现没有，回到步骤3
5. 队列中弹出顶点5，遍历邻接表中与5相邻的未访问过的顶点，选择顶点6，将其标记为访问过，加入队列中
6. 队列中弹出顶点6，遍历邻接表中与6相邻的未访问过的顶点，发现没有，回到步骤5
7. 队列中弹出顶点3，遍历邻接表中与3相邻的未访问过的顶点，选择顶点5，将其标记为访问过，加入队列中
8. 队列中弹出顶点5，发现已经访问过，回到步骤2
9. 队列中弹出顶点2，发现已经访问过，回到步骤1
10. 队列中弹出顶点4，发现已经访问过，回到步骤1
11. 遍历结束

广度优先遍历的输出结果为：1 -> 2 -> 3 -> 4 -> 5 -> 6

### 回答2：
邻接表是一种表示图的数据结构，它通过一个数组来存储各个顶点，每个顶点都维护一个链表，链表中存储了与该顶点相邻的顶点。邻接表可以用来实现图的深度优先遍历和广度优先遍历。

以如下图为例：

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

深度优先遍历（DFS）：从起始顶点开始，沿着深度优先的方向依次访问图中的顶点。

使用邻接表表示该图时，可以从起始顶点1开始，首先访问与1相邻的顶点2，然后访问顶点2的相邻顶点4，再访问顶点4没有相邻顶点后回溯到顶点2，继续访问顶点2的另一个相邻顶点5，然后回溯到顶点1，访问顶点1的另一个相邻顶点3，接着访问顶点3的相邻顶点6，再访问顶点6的相邻顶点7。

所以，深度优先遍历的访问顺序为：1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7。

广度优先遍历（BFS）：从起始顶点开始，依次访问图中的顶点，先访问与起始顶点直接相邻的顶点，再依次访问与这些顶点相邻的顶点。

使用邻接表表示该图时，可以从起始顶点1开始，先访问与1相邻的顶点2和3，然后继续访问与顶点2和3相邻的顶点，依次访问顶点4、5、6和7。

所以，广度优先遍历的访问顺序为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

通过邻接表可以方便地实现图的深度优先遍历和广度优先遍历，它们在遍历顺序上有所不同，适用于不同的场景和问题。

### 回答3：
邻接表是一种图的表示方法，它使用一组链表来表示图中每个顶点的邻接顶点。深度优先遍历（Depth First Search，DFS）和广度优先遍历（Breadth First Search，BFS）是常用的图遍历算法。

深度优先遍历是一种沿着图的深度方向进行遍历的算法。它从图的某个顶点开始，沿着一条未访问过的边进入下一个顶点，直到该顶点没有未访问过的边为止，然后返回上一层继续遍历。深度优先遍历使用堆栈（Stack）数据结构来实现。以下是一个深度优先遍历的例子：

假设有以下图的邻接表表示：
顶点1 -> 顶点2 -> 顶点3
顶点2 -> 顶点1 -> 顶点4 -> 顶点5
顶点3 -> 顶点1 -> 顶点6
顶点4 -> 顶点2
顶点5 -> 顶点2
顶点6 -> 顶点3

从顶点1开始进行深度优先遍历的过程如下：
1 -> 2 -> 4 -> 5 -> 3 -> 6

广度优先遍历是一种沿着图的广度方向进行遍历的算法。它从图的某个顶点开始，访问所有与该顶点邻接的顶点，然后再依次访问与这些邻接顶点相邻接的顶点，直到所有顶点都被访问为止。广度优先遍历使用队列（Queue）数据结构来实现。以下是一个广度优先遍历的例子：

假设有以下图的邻接表表示：
顶点1 -> 顶点2 -> 顶点3
顶点2 -> 顶点1 -> 顶点4 -> 顶点5
顶点3 -> 顶点1 -> 顶点6
顶点4 -> 顶点2
顶点5 -> 顶点2
顶点6 -> 顶点3

从顶点1开始进行广度优先遍历的过程如下：
1 -> 2 -> 3 -> 4 -> 5 -> 6

深度优先遍历和广度优先遍历在实际应用中有不同的用途。深度优先遍历更适合用于寻找目标节点在图中是否存在，而广度优先遍历更适合用于寻找目标节点与起始节点的最短路径。