数据结构与算法 / 系统课时
图的基本概念
图的基本概念
图用顶点表示对象,用边表示对象之间的关系。本课建立后续遍历与最短路径算法所需的统一术语,并通过一个小型无向图计算度数、连通分量和环,避免混淆“直接相连”“存在路径”和“属于同一分量”。
学习目标
- 区分有向图、无向图、加权图与无权图
- 理解度、路径、环、连通和连通分量
- 用代码验证一个图的基本结构信息
图的组成与分类
图通常记为 ,其中 是顶点集合, 是边集合。无向边 {A, B} 表示 A 与 B 的关系对称;有向边 (A, B) 表示从 A 指向 B,反向关系必须由另一条边单独表示。
边还可以携带权重,用于表示距离、耗时、费用或容量。无权图并非“没有成本”,而是算法把每条边视为等价,常可理解为每条边权重均为 1。

路径、环、连通与度
路径是相邻顶点依次通过边连接形成的序列。无向图中的 A-B-C 与 C-B-A 都是有效路径;有向图则必须遵循箭头方向。简单路径不重复经过顶点。
起点与终点相同、且至少包含一条边的闭合路径称为环。是否允许自环、是否允许重复顶点,要以具体算法的定义为准;初学阶段通常讨论不重复顶点的简单环。
在无向图中,若两个顶点之间存在路径,就称它们连通。彼此连通且无法再加入其他顶点的最大顶点集合称为连通分量。对有向图,还需区分忽略方向后的弱连通与双向均可达的强连通。
无向图中,顶点的度是与它相接的边数。一条普通无向边会让两个端点的度各加 1;自环通常对度贡献 2。
有向图分别统计入度和出度。边 A -> B 让 A 的出度加 1,让 B 的入度加 1。所有顶点入度之和与出度之和都等于边数。
主示例:统计结构信息
下面使用邻接集合表示一个无向图。示例不仅统计顶点度,还通过深度优先搜索计算连通分量,并判断指定的三个顶点是否构成三角环。
graph = {
"A": {"B", "C"},
"B": {"A", "C"},
"C": {"A", "B"},
"D": {"E"},
"E": {"D", "F"},
"F": {"E"},
}
def connected_components(adjacency):
visited = set()
components = []
for start in sorted(adjacency):
if start in visited:
continue
stack = [start]
visited.add(start)
component = []
while stack:
vertex = stack.pop()
component.append(vertex)
# 逆序压栈,使弹出后的访问顺序保持字母升序。
for neighbor in sorted(adjacency[vertex], reverse=True):
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
components.append(component)
return components
def forms_triangle(adjacency, first, second, third):
# 无向三角环要求三对顶点都直接相连。
return (
second in adjacency[first]
and third in adjacency[second]
and first in adjacency[third]
)
degrees = {vertex: len(neighbors) for vertex, neighbors in graph.items()}
edge_count = sum(degrees.values()) // 2
print("顶点数:", len(graph))
print("边数:", edge_count)
print("各顶点度:", dict(sorted(degrees.items())))
print("连通分量:", connected_components(graph))
print("A-B-C 构成三角环:", forms_triangle(graph, "A", "B", "C"))预期输出:
顶点数: 6
边数: 5
各顶点度: {'A': 2, 'B': 2, 'C': 2, 'D': 1, 'E': 2, 'F': 1}
连通分量: [['A', 'B', 'C'], ['D', 'E', 'F']]
A-B-C 构成三角环: True这里的“边数除以 2”只适用于不含特殊计数约定的无向图,因为每条边在两个端点的邻接集合中各记录一次。
“直接相连”要求两点之间存在一条边,“可达”只要求存在一条路径。两个顶点属于同一连通分量,并不意味着它们一定直接相邻。
有向边不能自动反向使用,边 A -> B 与 B -> A 是两条不同的边。加权图中还要区分“不存在边”和“边权为 0”,存储时不能总用同一个值表达两种状态。