Part 4.1：图论入门——图的表示与遍历 (BFS & DFS)
引言：万物皆可“图”
我们生活在一个充满连接的世界里。社交网络中，人与人是朋友关系；地图上，城市与城市通过道路相连；互联网中，网页与网页通过超链接互通。这些“实体”与“关系”构成的网络，在计算机科学中可以被抽象为一种强大的数据结构——**图 (Graph)**。
图论是算法领域皇冠上的一颗明珠，它为我们提供了一套完整的理论和工具，来分析和解决各种连接性问题。无论是寻找最短路径、规划网络布线，还是进行任务调度，都离不开图论的知识。
本系列文章将带你系统地学习图论的核心算法。作为开篇，我们将从最基础的问题入手：
- 如何在代码中表示一个图？
- 如何不重不漏地访问图中的所有节点？
图的基本概念
一个图 G 由顶点集 V (Vertices) 和边集 E (Edges) 组成，记为 G = (V, E)。
- **顶点 (Vertex)**：图中的一个节点，如社交网络中的用户、地图上的城市。
- **边 (Edge)**：连接两个顶点的线，代表它们之间的关系。
根据边的性质，图可以分为：
- **无向图 (Undirected Graph)**：边没有方向，
(u, v)和(v, u)是同一条边。 - **有向图 (Directed Graph)**：边有方向，
(u, v)表示从u到v的一条边，与(v, u)不同。 - **带权图 (Weighted Graph)**：每条边都有一个权重或成本，如城市间的距离。
图的表示方法
要在程序中处理图，我们首先需要一种方式来存储它。最常用的两种方法是邻接矩阵和邻接表。
1. 邻接矩阵 (Adjacency Matrix)
邻接矩阵是一个二维数组 adj，其中 adj[i][j] 表示从顶点 i 到顶点 j 是否有边。
- 对于无向图，如果
i和j之间有边，则adj[i][j] = adj[j][i] = 1。 - 对于有向图，如果存在从
i到j的边，则adj[i][j] = 1。 - 对于带权图，
adj[i][j]可以存储边的权重。
优点：
- 实现简单，直观。
- 查询两个顶点之间是否有边非常快，时间复杂度为
O(1)。
缺点：
- 空间复杂度高，为
O(V²)，其中V是顶点数。对于稀疏图（边数远小于V²），会造成巨大的空间浪费。 - 遍历一个顶点的所有邻居需要
O(V)的时间。
2. 邻接表 (Adjacency List)
邻接表是为图中的每个顶点维护一个列表，该列表存储了所有与该顶点相邻的顶点。
优点：
- 空间复杂度低，为
O(V + E)，其中E是边数。对于稀疏图非常高效。 - 遍历一个顶点的所有邻居非常快。
缺点：
- 查询两个顶点之间是否有边需要
O(degree(v))的时间，其中degree(v)是顶点的度（邻居数量）。
在算法竞赛和大多数实际应用中，邻接表是更常用和更高效的选择。
图的遍历
图的遍历是指从图的某个顶点出发，系统地访问图中的每一个顶点，且每个顶点只被访问一次。
1. 广度优先搜索 (Breadth-First Search, BFS)
BFS 是一种层序遍历，它从起始顶点开始，首先访问所有距离为 1 的邻居，然后是距离为 2 的邻居，以此类推，就像水波纹一样向外扩散。
核心思想：使用一个队列来实现。
步骤：
- 创建一个队列，并将起始顶点入队。
- 标记起始顶点为已访问。
- 当队列不为空时，循环执行：
a. 将队头顶点出队。
b. 访问该顶点的所有未被访问过的邻居。
c. 将这些邻居标记为已访问，并依次入队。
应用：
- 无权图的最短路径：BFS 找到的从起点到任何其他顶点的路径，都是最短的（边数最少）。
- 拓扑排序（将在后续文章中介绍）。
2. 深度优先搜索 (Depth-First Search, DFS)
DFS 是一种“一条路走到黑”的遍历方式。它从起始顶点开始，沿着一条路径不断深入，直到无法再前进时，才回溯到上一个节点，选择另一条路径继续探索。
核心思想：使用递归或栈来实现。
**步骤 (递归实现)**：
- 从起始顶点
u开始，标记u为已访问。 - 对于
u的每一个邻居v：
a. 如果v未被访问，则对v进行深度优先搜索。
应用：
- 寻找路径：判断两个顶点之间是否存在路径。
- 检测环路：在有向图和无向图中检测是否存在环。
- 寻找连通分量。
- 拓扑排序。
Python 实现
下面我们使用邻接表来实现 BFS 和 DFS。
from collections import deque, defaultdict
class Graph:
def __init__(self):
# 使用邻接表表示图
self.adj = defaultdict(list)
def add_edge(self, u, v):
"""添加一条从 u 到 v 的边 (对于无向图，应双向添加)"""
self.adj[u].append(v)
def bfs(self, start_node):
"""从 start_node 开始进行广度优先搜索"""
if start_node not in self.adj:
print("起始节点不存在")
return
visited = set()
queue = deque([start_node])
visited.add(start_node)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in self.adj[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(f"BFS 遍历结果: {result}")
return result
def dfs(self, start_node):
"""从 start_node 开始进行深度优先搜索"""
if start_node not in self.adj:
print("起始节点不存在")
return
visited = set()
result = []
def _dfs_recursive(node):
visited.add(node)
result.append(node)
for neighbor in self.adj[node]:
if neighbor not in visited:
_dfs_recursive(neighbor)
_dfs_recursive(start_node)
print(f"DFS 遍历结果: {result}")
return result
# --- 案例测试 ---
# 创建一个有向图
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('B', 'E')
g.add_edge('C', 'F')
# A
# / \
# B C
# / \ \
# D E F
print("从 'A' 开始遍历:")
g.bfs('A') # BFS 遍历结果: ['A', 'B', 'C', 'D', 'E', 'F']
g.dfs('A') # DFS 遍历结果: ['A', 'B', 'D', 'E', 'C', 'F'] (可能因邻接表顺序而异)总结
图的表示和遍历是整个图论算法的基石。几乎所有高级的图论算法，都是在 BFS 或 DFS 的框架上进行扩展和修改的。
本文核心要点
✅ 图的表示：邻接矩阵（O(V²) 空间，O(1) 查边）和邻接表（O(V+E) 空间，更常用）。
✅ 广度优先搜索 (BFS)：使用队列，按层次遍历，常用于求解无权图的最短路径。
✅ 深度优先搜索 (DFS)：使用递归或栈，一条路走到底，常用于路径查找、环检测和连通性问题。
掌握了这两种基本的遍历方法，你就拿到了开启图论算法大门的钥匙。在下一篇文章中，我们将学习图论中的一个经典问题——最小生成树，看看如何用最少的成本连接所有顶点。