面试题：Python数据结构与算法之图的遍历

Question

给定一个用邻接表表示的图，用Python实现深度优先搜索（DFS）和广度优先搜索（BFS）算法，并说明在什么场景下应该优先使用DFS，什么场景下应该优先使用BFS。

Answer 1

深度优先搜索（DFS）实现

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}


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)
    return visited

广度优先搜索（BFS）实现

from collections import deque


def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

适用场景

• DFS适用场景：
  • 当需要寻找深度路径，比如在迷宫问题中找到一条从起点到终点的路径时，DFS可能更合适。因为它会沿着一条路径尽可能深地探索下去，直到无法继续或达到目标。
  • 处理树状结构数据时，如果需要遍历整棵树，DFS相对简洁高效。比如文件系统树的遍历，在寻找特定文件或目录时，DFS可以快速深入到子目录查找。
• BFS适用场景：
  • 当需要寻找最短路径，比如在社交网络中找两个人之间的最短关系链，BFS能保证找到的路径是最短的。因为它是按层进行搜索，首先探索距离起始节点最近的节点。
  • 在网络拓扑中寻找广播路径等需要覆盖所有节点且要求路径尽量短的场景，BFS是更好的选择。