第9章 图的基本概念与存储
9.1 图的基本概念
图（Graph）是一种由顶点（Vertex） 和边（Edge） 组成的非线性数据结构，用于描述多对多的关系。与树（一对多）和线性结构（一对一）不同，图中顶点之间的关系可以是任意的，广泛应用于社交网络、路线规划、电路设计等领域。
9.1.1 图的定义与分类
图的形式化定义：图 GGG 由顶点集 VVV 和边集 EEE 组成，记为 G=(V,E)G = (V, E)G=(V,E)。
o顶点集 VVV：非空有限集合，每个元素称为顶点（或节点）；
o边集 EEE：有限集合，每个元素称为边，边是顶点的无序对（无向图）或有序对（有向图）。
按边的方向分类
1.无向图（Undirected Graph）：
边是顶点的无序对，记为 (u,v)(u, v)(u,v)，其中 uuu 和 vvv 为顶点，且 (u,v)=(v,u)(u, v) = (v, u)(u,v)=(v,u)（边无方向）。
示例：社交网络中的“好友关系”（A是B的好友等价于B是A的好友）。
2.
有向图（Directed Graph）：
边是顶点的有序对，记为 <u,v><u, v><u,v>，称为从 uuu 到 vvv 的有向边（或弧），其中 uuu 为起点（弧尾），vvv 为终点（弧头），且 <u,v>≠<v,u><u, v> eq <v, u><u,v>=<v,u>（边有方向）。
示例：微博中的“关注关系”（A关注B不等价于B关注A）。
3.按边的权值分类
1.无权图（Unweighted Graph）：
边仅表示顶点间的连接关系，无附加信息。
2.带权图（Weighted Graph）：
边带有表示某种含义的数值（如距离、成本、权重），也称为网（Network）。
示例：地图中的“道路”（边的权值表示距离或时间）。
3.按顶点间的连接程度分类
1.完全图：
2.
o无向完全图：任意两个顶点间都存在边，含 nnn 个顶点的无向完全图有 n(n−1)/2n(n-1)/2n(n−1)/2 条边；
o有向完全图：任意两个顶点间都存在方向相反的两条有向边，含 nnn 个顶点的有向完全图有 n(n−1)n(n-1)n(n−1) 条边。
3.
稀疏图与稠密图：
4.
o边数远小于完全图边数的图称为稀疏图（通常 E<nlog⁡nE < nlog nE<nlogn）；
o边数接近完全图边数的图称为稠密图。
9.1.2 图的基本术语
以下术语以图9-1的无向图 G1G_1G1​ 和有向图 G2G_2G2​ 为例说明：
G₁（无向图）： G₂（有向图）：
V = {A,B,C,D} V = {A,B,C,D}
E = {(A,B), (A,C), (B,C), (B,D)} E = {<A,B>, <B,A>, <B,C>, <C,D>}

A --- B → D A ←→ B → C → D 
| | 
| | 
C -----

图9-1 无向图与有向图示例
顶点与边的关系

关联（Incident）：若边 eee 连接顶点 uuu 和 vvv，则称 eee 与 uuu、vvv 关联。
如 G1G_1G1​ 中边 (A,B)(A,B)(A,B) 关联顶点 AAA 和 BBB。


邻接（Adjacent）：若顶点 uuu 和 vvv 之间存在边，则称 uuu 与 vvv 邻接。
如 G1G_1G1​ 中 AAA 与 BBB 邻接，G2G_2G2​ 中 BBB 与 CCC 邻接（但 CCC 与 BBB 不邻接，因边是有向的）。

顶点的度

无向图：顶点 vvv 的度（Degree）是与 vvv 关联的边数，记为 deg(v)deg(v)deg(v)。
如 G1G_1G1​ 中 deg(B)=3deg(B) = 3deg(B)=3（关联边 (A,B),(B,C),(B,D)(A,B), (B,C), (B,D)(A,B),(B,C),(B,D)）。


有向图：

o入度（In-degree）：以 vvv 为终点的有向边数，记为 indeg(v)indeg(v)indeg(v)；
o出度（Out-degree）：以 vvv 为起点的有向边数，记为 outdeg(v)outdeg(v)outdeg(v)；
o顶点 vvv 的度 deg(v)=indeg(v)+outdeg(v)deg(v) = indeg(v) + outdeg(v)deg(v)=indeg(v)+outdeg(v)。
如 G2G_2G2​ 中 indeg(A)=1indeg(A) = 1indeg(A)=1（边 <B,A><B,A><B,A>），outdeg(B)=2outdeg(B) = 2outdeg(B)=2（边 <B,A>,<B,C><B,A>, <B,C><B,A>,<B,C>），deg(B)=1+2=3deg(B) = 1 + 2 = 3deg(B)=1+2=3。
性质：任意无向图中，所有顶点的度之和等于边数的2倍（每条边关联两个顶点）；有向图中，所有顶点的入度之和等于出度之和（每条有向边对应一个入度和一个出度）。
路径与回路

路径（Path）：由顶点和边交替组成的序列，其中每条边关联相邻两个顶点。

o路径长度：路径中边的数量。
o简单路径：路径中顶点不重复（如 G1G_1G1​ 中 A→B→DA→B→DA→B→D 是简单路径，长度2）。

回路（Cycle）：起点和终点相同的路径，且除起点外顶点不重复（如 G1G_1G1​ 中 A→B→C→AA→B→C→AA→B→C→A 是回路，长度3）。

连通性

无向图：

o连通：若顶点 uuu 和 vvv 之间存在路径，则称 uuu 和 vvv 连通；
o连通图：图中任意两个顶点都连通（如 G1G_1G1​ 是连通图）；
o连通分量：极大连通子图（非连通图可分解为多个连通分量）。

有向图：

o强连通：若顶点 uuu 和 vvv 之间存在双向路径（从 uuu 到 vvv 且从 vvv 到 uuu），则称 uuu 和 vvv 强连通；
o强连通图：图中任意两个顶点都强连通（如 G2G_2G2​ 不是强连通图，因 AAA 到 CCC 无路径）；
o强连通分量：极大强连通子图。
子图与生成树

子图（Subgraph）：若图 G′G'G′ 的顶点集和边集均为图 GGG 的子集，则称 G′G'G′ 是 GGG 的子图。


生成树（Spanning Tree）：连通图的极小连通子图，包含所有顶点且边数最少（n−1n-1n−1 条边，nnn 为顶点数）。
生成树无回路，若添加一条边则形成回路；若删除一条边则不再连通。

9.2 图的存储结构
图的存储需完整表示顶点集和边集，核心挑战是高效存储顶点间的关联关系。常用存储结构包括邻接矩阵和邻接表，分别适用于稠密图和稀疏图。
9.2.1 邻接矩阵（Adjacency Matrix）
思想：用二维数组（矩阵）存储顶点间的邻接关系，矩阵的行和列对应顶点，矩阵元素表示边是否存在（或权值）。
无向图的邻接矩阵
设无向图有 nnn 个顶点，顶点编号为 0,1,...,n−10, 1, ..., n-10,1,...,n−1，邻接矩阵 AAA 定义为：
A[i][j]={1若顶点 i 与 j 邻接（存在边）0否则 A[i][j] = egin{cases} 1 & ext{若顶点 } i ext{ 与 } j ext{ 邻接（存在边）} 0 & ext{否则} end{cases} A[i][j]={10​若顶点 i 与 j 邻接（存在边）否则​
示例：G1G_1G1​（顶点 A,B,C,DA,B,C,DA,B,C,D 编号为0,1,2,3）的邻接矩阵为：
A=[0110101111000100] A = egin{bmatrix} 0 & 1 & 1 & 0 % A(0)的邻接顶点：B(1), C(2) 1 & 0 & 1 & 1 % B(1)的邻接顶点：A(0), C(2), D(3) 1 & 1 & 0 & 0 % C(2)的邻接顶点：A(0), B(1) 0 & 1 & 0 & 0 % D(3)的邻接顶点：B(1) end{bmatrix} A=​0110​1011​1100​0100​​
特点：
对称矩阵（A[i][j]=A[j][i]A[i][j] = A[j][i]A[i][j]=A[j][i]），可仅存储上（或下）三角部分节省空间；
顶点 iii 的度为第 iii 行（或列）元素之和（如 B(1)B(1)B(1) 的度为 1+0+1+1=31+0+1+1=31+0+1+1=3）；
空间复杂度 O(n2)O(n^2)O(n2)，适合稠密图。
有向图的邻接矩阵
有向图的邻接矩阵 AAA 定义为：
A[i][j]={1若存在从顶点 i 到 j 的有向边0否则 A[i][j] = egin{cases} 1 & ext{若存在从顶点 } i ext{ 到 } j ext{ 的有向边} 0 & ext{否则} end{cases} A[i][j]={10​若存在从顶点 i 到 j 的有向边否则​
示例：G2G_2G2​（顶点编号同上）的邻接矩阵为：
A=[0100101000010000] A = egin{bmatrix} 0 & 1 & 0 & 0 % A(0)的出边：B(1) 1 & 0 & 1 & 0 % B(1)的出边：A(0), C(2) 0 & 0 & 0 & 1 % C(2)的出边：D(3) 0 & 0 & 0 & 0 % D(3)无出边 end{bmatrix} A=​0100​1000​0100​0010​​
特点：
非对称矩阵（A[i][j]≠A[j][i]A[i][j] eq A[j][i]A[i][j]=A[j][i]）；
顶点 iii 的出度为第 iii 行元素之和，入度为第 iii 列元素之和（如 B(1)B(1)B(1) 的出度为 1+0+1+0=21+0+1+0=21+0+1+0=2，入度为 111（第1列 A[0][1]=1A[0][1] = 1A[0][1]=1））。
带权图的邻接矩阵
带权图（网）的邻接矩阵元素存储边的权值，非邻接顶点用特殊值（如 ∞infty∞ 或0）表示：
A[i][j]={w若顶点 i 与 j 邻接，且边权为 w∞否则（非邻接）0顶点 i=j（对角线，自身到自身） A[i][j] = egin{cases} w & ext{若顶点 } i ext{ 与 } j ext{ 邻接，且边权为 } w infty & ext{否则（非邻接）} 0 & ext{顶点 } i = j ext{（对角线，自身到自身）} end{cases} A[i][j]=⎩⎨⎧​w∞0​若顶点 i 与 j 邻接，且边权为 w否则（非邻接）顶点 i=j（对角线，自身到自身）​
示例：带权无向图的邻接矩阵（权值表示距离）：
A=[053∞5024320∞∞4∞0] A = egin{bmatrix} 0 & 5 & 3 & infty 5 & 0 & 2 & 4 3 & 2 & 0 & infty infty & 4 & infty & 0 end{bmatrix} A=​053∞​5024​320∞​∞4∞0​​
9.2.2 邻接表（Adjacency List）
思想：用数组存储顶点信息，每个顶点关联一个链表（或动态数组），存储与该顶点邻接的顶点（或边信息）。
无向图的邻接表
顶点表：数组 vertices，每个元素存储顶点数据；
邻接表：每个顶点对应一个链表 adj[i]，存储与顶点 iii 邻接的顶点编号（或指针）。
示例：G1G_1G1​ 的邻接表表示（顶点编号0,1,2,3）：

	vertices: [A, B, C, D] 
	adj[0]: 1 → 2 % A的邻接顶点：B(1), C(2) 
	adj[1]: 0 → 2 → 3 % B的邻接顶点：A(0), C(2), D(3) 
	adj[2]: 0 → 1 % C的邻接顶点：A(0), B(1) 
	adj[3]: 1 % D的邻接顶点：B(1)

特点：
无向图中，每条边在邻接表中出现两次（如边 (A,B)(A,B)(A,B) 同时出现在 adj[0] 和 adj[1]）；
顶点 iii 的度为 adj[i] 的长度（如 adj[1] 长度为3，对应 BBB 的度为3）；
空间复杂度 O(n+2e)O(n + 2e)O(n+2e)（eee 为边数），适合稀疏图。
有向图的邻接表
有向图的邻接表分为出边表（存储出度邻接顶点）和入边表（存储入度邻接顶点，也称逆邻接表）：
出边表：adj[i] 存储从顶点 iii 出发的有向边终点；
入边表：reverse_adj[i] 存储以顶点 iii 为终点的有向边起点。
示例：G2G_2G2​ 的出边表和入边表：
出边表：

	adj[0]: 1 % A的出边：B(1) 
	adj[1]: 0 → 2 % B的出边：A(0), C(2) 
	adj[2]: 3 % C的出边：D(3) 
	adj[3]: (空) 
	
	入边表： 
	reverse_adj[0]: 1 % A的入边：B(1) 
	reverse_adj[1]: 0 % B的入边：A(0) 
	reverse_adj[2]: 1 % C的入边：B(1) 
	reverse_adj[3]: 2 % D的入边：C(2)

特点：
出边表中 adj[i] 的长度为顶点 iii 的出度，入边表中 reverse_adj[i] 的长度为入度；
空间复杂度 O(n+e)O(n + e)O(n+e)（有向图中每条边仅出现一次）。
带权图的邻接表
带权图的邻接表节点需同时存储邻接顶点编号和边的权值，通常用结构体或元组表示：
python

	# 带权邻接表示例（Python列表+元组） 
	adj = [ 
	[(1, 5), (2, 3)], # 顶点0的邻接顶点：(1,权5), (2,权3) 
	[(0, 5), (2, 2), (3, 4)], # 顶点1的邻接顶点 
	[(0, 3), (1, 2)], # 顶点2的邻接顶点 
	[(1, 4)] # 顶点3的邻接顶点 
	]

9.2.3 邻接矩阵 vs 邻接表

实现难度 简单（二维数组） 较复杂（数组+链表/列表）
9.2.4 其他存储结构
邻接多重表：优化无向图的邻接表，解决同一条边存储两次的问题，适合频繁删除边的场景；
十字链表：结合邻接表和逆邻接表，适合有向图的出度和入度同时查询的场景；
边集数组：用数组存储所有边（每条边含起点、终点、权值），适合边的批量处理（如Kruskal算法），但查询效率低。
9.3 图的基本操作
图的基本操作围绕顶点和边的增删查改，以下基于邻接表实现核心操作（以无向图为例）：
9.3.1 初始化图
python

	class GraphAdjList: 
	def __init__(self, num_vertices: int): 
	self.num_vertices = num_vertices # 顶点数 
	self.adj = [[] for _ in range(num_vertices)] # 邻接表（列表的列表） 
	
	def add_edge(self, u: int, v: int): 
	"""添加无向边 (u, v)""" 
	if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: 
	self.adj[u].append(v) 
	self.adj[v].append(u) # 无向图需添加双向 
	
	def remove_edge(self, u: int, v: int): 
	"""删除无向边 (u, v)""" 
	if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: 
	self.adj[u] = [x for x in self.adj[u] if x != v] 
	self.adj[v] = [x for x in self.adj[v] if x != u] 
	
	def get_neighbors(self, u: int) -> list[int]: 
	"""获取顶点 u 的所有邻接顶点""" 
	if 0 <= u < self.num_vertices: 
	return self.adj[u] 
	return []

9.3.2 示例使用
python

	# 创建含4个顶点的无向图（对应 G₁） 
	g = GraphAdjList(4) 
	g.add_edge(0, 1) # A-B 
	g.add_edge(0, 2) # A-C 
	g.add_edge(1, 2) # B-C 
	g.add_edge(1, 3) # B-D 
	
	print(g.get_neighbors(1)) # 输出 [0, 2, 3]（B的邻接顶点：A, C, D）

9.4 总结
本章介绍了图的基本概念和存储结构，核心要点如下：
图的定义：由顶点集和边集组成，分为无向图/有向图、无权图/带权图等，顶点间关系通过度、路径、连通性描述；
存储结构：
o邻接矩阵：二维数组存储邻接关系，适合稠密图，查询效率高（O(1)O(1)O(1)），空间复杂度 O(n2)O(n^2)O(n2)；
o邻接表：数组+链表存储邻接关系，适合稀疏图，空间效率高（O(n+e)O(n + e)O(n+e)），遍历效率高。
图的存储是后续图遍历（DFS/BFS）、最短路径（Dijkstra/Floyd）、最小生成树（Prim/Kruskal）等算法的基础，需根据实际场景（图的稠密程度、操作类型）选择合适的存储结构。
第9章 图的基本概念与存储
9.1 图的基本概念
9.1.1 图的定义
图（Graph）是由顶点集（Vertex Set） 和边集（Edge Set） 组成的非线性数据结构，记为 G=(V,E)G=(V,E)G=(V,E)。其中：
VVV 是顶点的非空有限集合，每个元素称为顶点（Vertex）；
EEE 是边的有限集合，每条边是顶点的无序对（无向图）或有序对（有向图），表示顶点间的连接关系。
与其他结构的区别：
线性结构（如数组、链表）：元素间为“一对一”关系；
树结构：元素间为“一对多”层次关系；
图结构：元素间为“多对多”任意关系，是最通用的数据结构之一。
9.1.2 图的分类
按边的方向划分
1.
无向图（Undirected Graph）
边是顶点的无序对，记为 (u,v)(u,v)(u,v)，其中 uuu 和 vvv 为顶点，且 (u,v)=(v,u)(u,v)=(v,u)(u,v)=(v,u)（边无方向）。
示例：社交网络中的“好友关系”（A与B为好友等价于B与A为好友）。
2.
3.
有向图（Directed Graph）
边是顶点的有序对，记为 <u,v><u,v><u,v>（称为“弧”），其中 uuu 为起点（弧尾），vvv 为终点（弧头），且 <u,v>≠<v,u><u,v> eq<v,u><u,v>=<v,u>（边有方向）。
示例：微博中的“关注关系”（A关注B不等价于B关注A）。
4.
按边的权值划分
1.
无权图（Unweighted Graph）
边仅表示顶点间的连接关系，无附加信息。
2.
3.
带权图（Weighted Graph）
边关联一个数值（如距离、成本、权重），也称网（Network）。
示例：地图中的“道路”（边的权值表示两地距离）。
4.
按顶点连接程度划分
1.
完全图
2.
o无向完全图：任意两顶点间均存在边，含 nnn 个顶点的无向完全图有 n(n−1)/2n(n-1)/2n(n−1)/2 条边；
o有向完全图：任意两顶点间均存在方向相反的两条弧，含 nnn 个顶点的有向完全图有 n(n−1)n(n-1)n(n−1) 条边。
3.
稀疏图与稠密图
4.
o边数远小于完全图边数的图称为稀疏图（通常 ∣E∣<nlog⁡n|E|<nlog n∣E∣<nlogn）；
o边数接近完全图边数的图称为稠密图。
9.2 图的基本术语
以下术语基于图9-1的无向图 G1G_1G1​ 和有向图 G2G_2G2​ 示例说明：
无向图 G1G_1G1​：V={A,B,C,D}V={A,B,C,D}V={A,B,C,D}，E={(A,B),(A,C),(B,C),(B,D)}E={(A,B),(A,C),(B,C),(B,D)}E={(A,B),(A,C),(B,C),(B,D)}
结构描述：顶点A连接B、C；B连接A、C、D；C连接A、B；D连接B。
有向图 G2G_2G2​：V={A,B,C,D}V={A,B,C,D}V={A,B,C,D}，E={<A,B>,<B,A>,<B,C>,<C,D>}E={<A,B>,<B,A>,<B,C>,<C,D>}E={<A,B>,<B,A>,<B,C>,<C,D>}
结构描述：A→B，B→A，B→C，C→D。
9.2.1 顶点与边的关系

关联（Incident）：边与顶点的连接关系。若边 eee 连接 uuu 和 vvv，则 eee 与 uuu、vvv 关联。
例：G1G_1G1​ 中边 (A,B)(A,B)(A,B) 关联顶点A和B。


邻接（Adjacent）：顶点间通过边直接连接的关系。若存在边连接 uuu 和 vvv，则 uuu 与 vvv 邻接。
例：G1G_1G1​ 中A与B邻接；G2G_2G2​ 中B→C，则B与C邻接（C与B不邻接，因无C→B的弧）。

9.2.2 顶点的度

无向图：顶点 vvv 的度（Degree） 是与 vvv 关联的边数，记为 deg(v)deg(v)deg(v)。
例：G1G_1G1​ 中 deg(B)=3deg(B)=3deg(B)=3（关联边 (A,B),(B,C),(B,D)(A,B),(B,C),(B,D)(A,B),(B,C),(B,D)）。


有向图：

o入度（In-degree）：以 vvv 为终点的弧数，记为 indeg(v)indeg(v)indeg(v)；
o出度（Out-degree）：以 vvv 为起点的弧数，记为 outdeg(v)outdeg(v)outdeg(v)；
o总度 deg(v)=indeg(v)+outdeg(v)deg(v)=indeg(v)+outdeg(v)deg(v)=indeg(v)+outdeg(v)。
例：G2G_2G2​ 中 indeg(A)=1indeg(A)=1indeg(A)=1（弧 <B,A><B,A><B,A>），outdeg(B)=2outdeg(B)=2outdeg(B)=2（弧 <B,A>,<B,C><B,A>,<B,C><B,A>,<B,C>），deg(B)=1+2=3deg(B)=1+2=3deg(B)=1+2=3。
性质：无向图中所有顶点的度之和为边数的2倍（每条边关联两顶点）；有向图中所有顶点的入度之和等于出度之和（每条弧对应一个入度和一个出度）。
9.2.3 路径与回路

路径（Path）：由顶点和边交替组成的序列，路径长度为边的数量。

o简单路径：路径中顶点不重复。
例：G1G_1G1​ 中 A→B→DA→B→DA→B→D 是简单路径（长度2）。

回路（Cycle）：起点与终点相同的路径，且除起点外顶点不重复。
例：G1G_1G1​ 中 A→B→C→AA→B→C→AA→B→C→A 是回路（长度3）。

9.2.4 连通性

无向图：

o连通：若两顶点间存在路径，则称它们连通；
o连通图：任意两顶点均连通的图；
o连通分量：极大连通子图（非连通图可分解为多个连通分量）。

有向图：

o强连通：若两顶点间存在双向路径（互为起点和终点），则称它们强连通；
o强连通图：任意两顶点均强连通的图；
o强连通分量：极大强连通子图。
9.2.5 子图与生成树
子图（Subgraph）：顶点集和边集均为原图子集的图。
生成树（Spanning Tree）：连通图的极小连通子图，含所有顶点且边数为 n−1n-1n−1（nnn 为顶点数），无回路，删除任一边则不连通，添加任一边则形成回路。
9.3 图的存储结构
图的存储需完整表示顶点集和边集，核心是高效存储顶点间的邻接关系。常用结构为邻接矩阵和邻接表。
9.3.1 邻接矩阵（Adjacency Matrix）
定义
用 n×nn imes nn×n 二维数组（矩阵）存储顶点间的邻接关系，矩阵行、列对应顶点，元素表示边是否存在（或权值）。

1. 无向图的邻接矩阵
   设无向图含 nnn 个顶点（编号 0,1,...,n−10,1,...,n-10,1,...,n−1），邻接矩阵 AAA 定义为：
   A[i][j]={1若顶点 i 与 j 邻接0否则 A[i][j] = egin{cases} 1 & ext{若顶点 } i ext{ 与 } j ext{ 邻接} 0 & ext{否则} end{cases} A[i][j]={10​若顶点 i 与 j 邻接否则​
   示例：G1G_1G1​（顶点A,B,C,D编号0,1,2,3）的邻接矩阵：
   A=[0110101111000100] A = egin{bmatrix} 0 & 1 & 1 & 0 % A(0)邻接B(1)、C(2) 1 & 0 & 1 & 1 % B(1)邻接A(0)、C(2)、D(3) 1 & 1 & 0 & 0 % C(2)邻接A(0)、B(1) 0 & 1 & 0 & 0 % D(3)邻接B(1) end{bmatrix} A=​0110​1011​1100​0100​​
   特点：
   对称矩阵（A[i][j]=A[j][i]A[i][j]=A[j][i]A[i][j]=A[j][i]），可仅存上/下三角节省空间；
   顶点 iii 的度为第 iii 行（列）元素之和（如 B(1)B(1)B(1) 的度为 1+0+1+1=31+0+1+1=31+0+1+1=3）；
   空间复杂度 O(n2)O(n^2)O(n2)，适合稠密图。
2. 有向图的邻接矩阵
   有向图邻接矩阵 AAA 定义为：
   A[i][j]={1若存在弧 <i,j>0否则 A[i][j] = egin{cases} 1 & ext{若存在弧 } <i,j> 0 & ext{否则} end{cases} A[i][j]={10​若存在弧 <i,j>否则​
   示例：G2G_2G2​ 的邻接矩阵：
   A=[0100101000010000] A = egin{bmatrix} 0 & 1 & 0 & 0 % A(0)出弧：B(1) 1 & 0 & 1 & 0 % B(1)出弧：A(0)、C(2) 0 & 0 & 0 & 1 % C(2)出弧：D(3) 0 & 0 & 0 & 0 % D(3)无出弧 end{bmatrix} A=​0100​1000​0100​0010​​
   特点：
   非对称矩阵；
   顶点 iii 的出度为第 iii 行元素之和，入度为第 iii 列元素之和（如 B(1)B(1)B(1) 出度 1+0+1+0=21+0+1+0=21+0+1+0=2，入度 111（第1列 A[0][1]=1A[0][1]=1A[0][1]=1））。
3. 带权图的邻接矩阵
   带权图（网）的矩阵元素存储边的权值，非邻接顶点用 ∞infty∞（或0）表示：
   A[i][j]={w若边 (i,j) 权值为 w∞否则0若 i=j（自身到自身） A[i][j] = egin{cases} w & ext{若边 } (i,j) ext{ 权值为 } w infty & ext{否则} 0 & ext{若 } i=j ext{（自身到自身）} end{cases} A[i][j]=⎩⎨⎧​w∞0​若边 (i,j) 权值为 w否则若 i=j（自身到自身）​
   示例：带权无向图（权值为距离）的邻接矩阵：
   A=[053∞5024320∞∞4∞0] A = egin{bmatrix} 0 & 5 & 3 & infty 5 & 0 & 2 & 4 3 & 2 & 0 & infty infty & 4 & infty & 0 end{bmatrix} A=​053∞​5024​320∞​∞4∞0​​
   9.3.2 邻接表（Adjacency List）
   定义
   用数组存储顶点信息，每个顶点关联一个链表（或动态数组），存储与该顶点邻接的顶点（或边信息）。
4. 无向图的邻接表
   顶点表：数组 vertices 存储顶点数据；
   邻接表：数组 adj，adj[i] 存储顶点 iii 的所有邻接顶点编号。
   示例：G1G_1G1​ 的邻接表（Python列表实现）：
   python

	vertices = ['A', 'B', 'C', 'D'] # 顶点表 
	adj = [ 
	[1, 2], # A(0)的邻接顶点：B(1)、C(2) 
	[0, 2, 3], # B(1)的邻接顶点：A(0)、C(2)、D(3) 
	[0, 1], # C(2)的邻接顶点：A(0)、B(1) 
	[1] # D(3)的邻接顶点：B(1) 
	]

特点：
每条边在邻接表中出现两次（如边 (A,B)(A,B)(A,B) 同时在 adj[0] 和 adj[1]）；
顶点 iii 的度为 adj[i] 的长度（如 adj[1] 长度3，对应 deg(B)=3deg(B)=3deg(B)=3）；
空间复杂度 O(n+2e)O(n+2e)O(n+2e)（eee 为边数），适合稀疏图。
2. 有向图的邻接表
有向图邻接表分出边表（存储出弧终点）和入边表（存储入弧起点，也称逆邻接表）。
示例：G2G_2G2​ 的出边表和入边表：
python

	# 出边表（存储出弧终点） 
	out_adj = [ 
	[1], # A(0)出弧：B(1) 
	[0, 2], # B(1)出弧：A(0)、C(2) 
	[3], # C(2)出弧：D(3) 
	[] # D(3)无出弧 
	] 
	
	# 入边表（存储入弧起点） 
	in_adj = [ 
	[1], # A(0)入弧：B(1)（弧 <B,A>） 
	[0], # B(1)入弧：A(0)（弧 <A,B>） 
	[1], # C(2)入弧：B(1)（弧 <B,C>） 
	[2] # D(3)入弧：C(2)（弧 <C,D>） 
	]

特点：
出边表中 out_adj[i] 长度为顶点 iii 的出度，入边表中 in_adj[i] 长度为入度；
空间复杂度 O(n+e)O(n+e)O(n+e)（有向图每条弧仅存一次）。
3. 带权图的邻接表
带权图的邻接表节点需存储邻接顶点编号和权值，常用元组 (邻接顶点, 权值) 表示。
示例：带权无向图的邻接表：
python

	adj = [ 
	[(1, 5), (2, 3)], # 顶点0邻接顶点1（权5）、2（权3） 
	[(0, 5), (2, 2), (3, 4)], # 顶点1邻接顶点0（权5）、2（权2）、3（权4） 
	[(0, 3), (1, 2)], # 顶点2邻接顶点0（权3）、1（权2） 
	[(1, 4)] # 顶点3邻接顶点1（权4） 
	]

9.3.3 邻接矩阵与邻接表对比

适用场景 稠密图、频繁判断邻接关系 稀疏图、频繁遍历邻接顶点
9.4 图的基本操作
以邻接表为存储结构，实现图的初始化、添加边、删除边、获取邻接顶点等基本操作（Python实现）。
9.4.1 无向无权图的邻接表实现
python

	class UndirectedGraph: 
	def __init__(self, num_vertices: int): 
	self.num_vertices = num_vertices # 顶点数 
	self.adj = [[] for _ in range(num_vertices)] # 邻接表（列表的列表） 
	
	def add_edge(self, u: int, v: int) -> None: 
	"""添加无向边 (u, v)""" 
	if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: 
	self.adj[u].append(v) 
	self.adj[v].append(u) # 无向图需双向添加 
	
	def remove_edge(self, u: int, v: int) -> None: 
	"""删除无向边 (u, v)""" 
	if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices: 
	self.adj[u] = [x for x in self.adj[u] if x != v] # 移除u的邻接v 
	self.adj[v] = [x for x in self.adj[v] if x != u] # 移除v的邻接u 
	
	def get_neighbors(self, u: int) -> list[int]: 
	"""获取顶点u的所有邻接顶点""" 
	if 0 <= u < self.num_vertices: 
	return self.adj[u] 
	return [] 
	
	def __str__(self) -> str: 
	"""打印邻接表""" 
	return '
'.join([f"Vertex {i}: {self.adj[i]}" for i in range(self.num_vertices)])

9.4.2 操作示例
python

	# 创建含4个顶点的无向图（对应 G₁） 
	g = UndirectedGraph(4) 
	g.add_edge(0, 1) # 添加边 (A,B) 
	g.add_edge(0, 2) # 添加边 (A,C) 
	g.add_edge(1, 2) # 添加边 (B,C) 
	g.add_edge(1, 3) # 添加边 (B,D) 
	
	print("邻接表:") 
	print(g) 
	# 输出： 
	# Vertex 0: [1, 2] 
	# Vertex 1: [0, 2, 3] 
	# Vertex 2: [0, 1] 
	# Vertex 3: [1] 
	
	print("
B的邻接顶点:", g.get_neighbors(1)) # 输出 [0, 2, 3] 
	
	g.remove_edge(1, 3) # 删除边 (B,D) 
	print("
删除(B,D)后邻接表:") 
	print(g) 
	# 输出： 
	# Vertex 0: [1, 2] 
	# Vertex 1: [0, 2] 
	# Vertex 2: [0, 1] 
	# Vertex 3: []

9.5 总结
本章介绍了图的基本概念、术语、存储结构及操作，核心要点如下：
1.图的定义与分类：图由顶点集和边集组成，按边的方向分为无向图/有向图，按权值分为无权图/带权图，按连接程度分为完全图/稀疏图/稠密图。
2.基本术语：顶点的度（无向图的度、有向图的入度/出度）、路径与回路、连通性（连通分量、强连通分量）、生成树等是描述图结构的基础。
3.存储结构：
o邻接矩阵：二维数组存储邻接关系，空间复杂度 O(n2)O(n^2)O(n2)，适合稠密图和频繁判断邻接的场景；
o邻接表：数组+链表存储邻接关系，空间复杂度 O(n+e)O(n+e)O(n+e)，适合稀疏图和频繁遍历邻接顶点的场景。
4.基本操作：基于邻接表可高效实现边的添加、删除和邻接顶点查询，是后续图算法（遍历、最短路径等）的基础。
图的存储结构选择需结合图的稠密程度和操作需求，合理选择可显著提升算法效率。下一章将介绍图的遍历算法（DFS和BFS）。

本站原创,转载请注明出处:https://www.xin3721.com/python3/python49270.html