数据结构与算法 / 系统课时
图的基本概念
图的基本概念
图用于描述对象及其关系。学会区分顶点、边、方向、权重、路径、环与连通分量后,你才能准确阅读图算法,并为后续的广度优先搜索和深度优先搜索选择合适的数据结构。
学习目标
- 能区分有向图、无向图、加权图与无权图。
- 能判断路径、简单路径、环、度、入度和出度。
- 能识别无向图的连通分量,并理解有向图中的可达性。
顶点、边与图的类型
图通常记为 ,其中 是顶点集合, 是边集合。顶点表示对象,边表示对象之间的关系。无向边 {u, v} 表示关系没有方向;有向边 (u, v) 表示只能从 u 指向 v。
| 图的类型 | 边的含义 | 典型场景 |
|---|---|---|
| 无向图 | 关系双向成立 | 好友关系、双向道路 |
| 有向图 | 关系具有方向 | 关注关系、任务依赖 |
| 加权图 | 每条边带成本或距离 | 路线规划、网络延迟 |
| 无权图 | 只关心是否相连 | 社交连接、网页链接 |
在无向图中,顶点的度是与它相接的边数。在有向图中,需要分别统计入度和出度:入度表示指向该顶点的边数,出度表示从该顶点发出的边数。

路径、环与连通性
路径是一串顶点序列,相邻顶点之间必须存在对应边。若路径中顶点不重复,称为简单路径;若起点与终点相同,并且至少经过一条边,则形成环。有向图中的路径必须遵循箭头方向。
无向图中,任意两个顶点之间都存在路径时,图是连通图。若整张图不连通,可以把顶点划分为若干连通分量,每个分量内部互相可达,不同分量之间没有路径。有向图还要区分单向可达与强连通,不能直接套用无向图的结论。
邻接表表示
下面用邻接表保存一个无向加权图。图中 A、B、C 构成一个连通分量,D、E 构成另一个连通分量。
python
from collections import deque
def build_graph(vertices, edges):
graph = {vertex: [] for vertex in vertices}
# 无向边需要同时写入两个端点的邻接表
for left, right, weight in edges:
graph[left].append((right, weight))
graph[right].append((left, weight))
for vertex in graph:
graph[vertex].sort()
return graph
def connected_components(graph):
visited = set()
components = []
for start in sorted(graph):
if start in visited:
continue
queue = deque([start])
visited.add(start)
component = []
# 从一个未访问顶点出发,收集整个连通分量
while queue:
vertex = queue.popleft()
component.append(vertex)
for neighbor, _ in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
components.append(component)
return components
def main():
vertices = ["A", "B", "C", "D", "E"]
edges = [
("A", "B", 2),
("B", "C", 1),
("D", "E", 3),
]
graph = build_graph(vertices, edges)
print("邻接表:")
for vertex in sorted(graph):
neighbors = ", ".join(
f"{neighbor}({weight})" for neighbor, weight in graph[vertex]
)
print(f"{vertex}: {neighbors}")
print("度数:")
for vertex in sorted(graph):
print(f"{vertex}: {len(graph[vertex])}")
print(f"连通分量: {connected_components(graph)}")
if __name__ == "__main__":
main()运行命令如下:
bash
python graph_basics.py预期输出
text
邻接表:
A: B(2)
B: A(2), C(1)
C: B(1)
D: E(3)
E: D(3)
度数:
A: 1
B: 2
C: 1
D: 1
E: 1
连通分量: [['A', 'B', 'C'], ['D', 'E']]易混淆点与练习
边数与度数不能直接混为一谈。无向图中,所有顶点度数之和等于边数的 2 倍;有向图中,所有顶点入度之和与出度之和都等于边数。路径也不等于简单路径,因为普通路径允许重复经过顶点或边。
练习 1:在示例图中增加边 C-D,预测连通分量数量和各顶点度数,再运行程序验证。
练习 2:把示例改成有向图,只把边写入起点的邻接表,并分别统计每个顶点的入度与出度。验收条件是输出的入度总和、出度总和都等于边数。
本课总结
- 图由顶点集合和边集合组成,方向与权重决定了边的语义。
- 路径、环、度和连通分量是描述图结构与可达性的基础概念。
- 邻接表适合表示稀疏图,也是后续 BFS 和 DFS 的常用存储结构。
下一课预告
下一阶段将学习图的具体表示方式,并比较邻接表与邻接矩阵在空间占用、查边效率和遍历方式上的差异。
按自己的节奏,确认真正理解。