图论基础和表示：从零开始理解图数据结构
在编程的世界里，数据结构是解决问题的基石。如果你接触过社交网络、导航系统、任务调度或者推荐算法，那几乎都离不开一种特殊的结构——图。图论基础和表示，正是我们理解这些复杂系统背后的数学模型与实现方式的第一步。
别被“图论”这个词吓到。它听起来像高等数学，其实本质就是描述“关系”的工具。想象一下，你和朋友之间的社交关系，或者城市之间的道路连接，都可以用图来建模。每个节点代表一个人或一座城市，每条边代表两人之间的朋友关系或两地之间的道路。
这种抽象能力，正是图数据结构的核心价值。掌握图论基础和表示，不仅能帮你写出更高效的算法，还能让你在面对现实世界问题时，更快地找到合适的建模思路。
什么是图？用生活场景来理解
在数学中，图（Graph）是由一组节点（Node）和一组连接这些节点的边（Edge）组成的结构。我们可以把它想象成一张“关系网”。
举个例子：假设你是一个大学社团的负责人，要组织一场活动。你需要通知所有成员，但不能一个个打电话。你决定通过“推荐”机制：每个人通知自己的朋友，朋友再通知朋友。这个过程，就是一个典型的图传播模型。
在这个模型里：
- 每个成员是一个节点（Node）
- 朋友关系是一条边（Edge）
- 通知传播的过程，就是图上的遍历操作
图可以是有向的，也可以是无向的。比如“你关注了他”是单向的（有向图），而“你们是朋友”是双向的（无向图）。这在建模真实世界时非常关键。
图的两种主要表示方式
在编程中，我们无法直接画图，必须用代码来表示图结构。最常用的两种方式是：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。
邻接矩阵：用二维数组“画图”
邻接矩阵是一种用二维数组来表示图的方式。数组的行和列分别代表图中的节点，matrix[i][j] 的值表示节点 i 和节点 j 之间是否有边。
matrix = [[0 for _ in range(5)] for _ in range(5)]
matrix[0][1] = 1
matrix[1][0] = 1 # 无向图，双向都要设置
matrix[1][2] = 1
matrix[2][1] = 1
matrix[2][3] = 1
matrix[3][2] = 1
matrix[3][4] = 1
matrix[4][3] = 1
for row in matrix:
print(row)
输出结果：
[0, 1, 0, 0, 0]
[1, 0, 1, 0, 0]
[0, 1, 0, 1, 0]
[0, 0, 1, 0, 1]
[0, 0, 0, 1, 0]
优点：判断两个节点是否相连非常快，时间复杂度 O(1)。
缺点：空间复杂度高，特别是节点很多但边很少时（稀疏图），会浪费大量内存。
邻接表：用列表的列表来“列名单”
邻接表是另一种更高效的表示方式。它用一个字典或数组，存储每个节点的“邻居列表”。
graph = {
0: [1],
1: [0, 2],
2: [1, 3],
3: [2, 4],
4: [3]
}
print("节点 1 的邻居:", graph[1]) # 输出: [0, 2]
graph[0].append(4)
graph[4].append(0)
print("添加边后，节点 0 的邻居:", graph[0]) # 输出: [1, 4]
优点：空间效率高，适合稀疏图。
缺点：判断两个节点是否相连需要遍历列表，时间复杂度 O(度数)。
💡 小建议：如果你的图节点很多（比如超过 1000 个），但边很少，优先使用邻接表。如果节点少（比如几十个），且需要频繁判断“是否有边”，邻接矩阵更方便。
有向图与无向图的代码实现对比
现实世界中，很多关系是有方向的。比如微博的“关注”关系：A 关注 B，但 B 不一定关注 A。
我们来用邻接表实现一个有向图。
directed_graph = {
'Alice': ['Bob'],
'Bob': ['Charlie'],
'Charlie': ['Alice', 'David'],
'David': []
}
def is_following(graph, a, b):
return b in graph.get(a, [])
print(is_following(directed_graph, 'Alice', 'Bob')) # True
print(is_following(directed_graph, 'Bob', 'Alice')) # False
而无向图的实现，只需要在添加边时双向更新即可：
undirected_graph = {}
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
# 双向添加
if b not in graph[a]:
graph[a].append(b)
if a not in graph[b]:
graph[b].append(a)
add_edge(undirected_graph, 'Alice', 'Bob')
add_edge(undirected_graph, 'Bob', 'Charlie')
add_edge(undirected_graph, 'Charlie', 'David')
print(undirected_graph)
图的边权重：不只是“有没有边”
在真实场景中，边往往不只是存在或不存在，还可能带有“权重”。比如地图上的道路，不仅有连接，还有距离、耗时或费用。
我们可以用字典来表示带权图，键是节点对，值是权重。
weighted_graph = {
('A', 'B'): 5,
('B', 'C'): 3,
('C', 'D'): 2,
('A', 'D'): 8,
('B', 'D'): 6
}
def get_weight(graph, a, b):
# 由于是无向图，(a,b) 和 (b,a) 视为相同
return graph.get((a, b), graph.get((b, a), None))
print("A 到 B 的距离:", get_weight(weighted_graph, 'A', 'B')) # 输出: 5
print("B 到 D 的距离:", get_weight(weighted_graph, 'B', 'D')) # 输出: 6
这种表示方式灵活，适合 Dijkstra 算法、最小生成树等图论算法。
常见图操作的代码示例
掌握图的表示后，我们来实现几个基础操作。
检查图中是否存在路径（DFS 遍历）
def has_path(graph, start, end, visited=None):
if visited is None:
visited = set()
# 如果当前节点已访问，跳过
if start in visited:
return False
# 标记当前节点为已访问
visited.add(start)
# 如果到达目标节点，返回 True
if start == end:
return True
# 递归访问所有邻居
for neighbor in graph.get(start, []):
if has_path(graph, neighbor, end, visited):
return True
return False
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D'],
'D': []
}
print(has_path(graph, 'A', 'D')) # True
print(has_path(graph, 'A', 'E')) # False
获取图中所有节点
def get_all_nodes(graph):
nodes = set()
for node in graph:
nodes.add(node)
for neighbor in graph[node]:
nodes.add(neighbor)
return nodes
print(get_all_nodes(graph)) # 输出: {'A', 'B', 'C', 'D'}
实际应用场景：社交网络与路径规划
图论基础和表示不仅仅停留在理论。在实际开发中，它无处不在：
- 社交网络：用户是节点，好友关系是边，推荐算法基于图的传播路径。
- 地图导航：城市是节点，道路是边，距离是权重，最短路径算法（如 Dijkstra）帮助你找到最优路线。
- 任务依赖调度：任务是节点，依赖关系是边，拓扑排序确保任务按正确顺序执行。
掌握这些基础，你就能在面对复杂系统时，迅速抽象出图模型，从而设计出高效算法。
总结：从零开始掌握图论基础和表示
图论基础和表示，是编程进阶路上的一座重要桥梁。它把现实世界中的“关系”抽象为可计算的结构，让复杂的系统变得清晰可解。
我们从图的基本概念讲起，介绍了邻接矩阵与邻接表两种主流表示方式，对比了它们的优劣。通过代码示例，你学会了如何表示有向图、无向图，以及带权图。最后，我们用 DFS 实现了路径查找，展示了图操作的实际应用。
记住：图不是“高深的数学”，而是“关系的表达”。当你下次看到“推荐”、“导航”、“依赖”这类词时，不妨想一想——这背后是不是一张图？
从今天开始，试着用图的视角看待问题。你会发现，世界比你想象的更“连通”。