如何遍历图？

推荐答案

遍历图的两种主要方法是深度优先搜索（DFS）和广度优先搜索（BFS）。以下是它们的实现：

深度优先搜索（DFS）

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 处理节点
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

广度优先搜索（BFS）

// www.javascriptcn.com code example
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node)  # 处理节点
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

本题详细解读

深度优先搜索（DFS）

深度优先搜索是一种递归的遍历方法，它从起始节点开始，沿着一条路径尽可能深入地访问节点，直到到达没有未访问邻居的节点，然后回溯并继续探索其他路径。DFS通常使用栈（递归调用栈）来实现。

• 优点：实现简单，适合用于寻找路径、拓扑排序等问题。
• 缺点：可能会陷入深度较大的路径，导致栈溢出。

广度优先搜索（BFS）

广度优先搜索是一种迭代的遍历方法，它从起始节点开始，逐层访问所有邻居节点，然后再访问邻居的邻居节点，依此类推。BFS通常使用队列来实现。

• 优点：适合用于寻找最短路径、连通分量等问题。
• 缺点：需要额外的空间来存储队列，空间复杂度较高。

选择DFS还是BFS？

• 如果需要寻找最短路径或最小步数，通常选择BFS。
• 如果需要探索所有可能的路径或进行拓扑排序，通常选择DFS。

图的表示

在代码中，图通常使用邻接表或邻接矩阵来表示。邻接表适合稀疏图，邻接矩阵适合稠密图。

// www.javascriptcn.com code example
# 邻接表表示法
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

时间复杂度

• DFS：O(V + E)，其中V是顶点数，E是边数。
• BFS：O(V + E)，其中V是顶点数，E是边数。

空间复杂度

• DFS：O(V)，递归调用栈的深度最多为V。
• BFS：O(V)，队列中最多存储V个节点。