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

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

邻接表的深度优先遍历（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 类型来实现。

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

假设我们有以下无向图的邻接表表示：

0: 1 -> 2
1: 0 -> 2 -> 3
2: 0 -> 1 -> 4
3: 1 -> 4
4: 2 -> 3

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

从节点0开始:
0 -> 1 -> 2 -> 4 -> 3

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

从节点0开始:
0 -> 1 -> 2 -> 3 -> 4

其中箭头表示遍历的路径。在DFS中，我们从起点开始，尽可能深入每个节点，直到遇到没有未访问的邻居节点为止，然后回溯到上一个未访问的节点并继续遍历。在BFS中，我们从起点开始，首先访问它的所有邻居节点，然后访问邻居节点的所有邻居节点，以此类推，直到遍历完整个图。