【数据结构与算法】图论

一、基础概念对比

概念 定义 重要性质 简单回路 顶点不重复的回路。回路是路径，简单回路是简单路径 是特殊的简单路径 极大连通子图 再添加任意顶点/边后不再连通的子图 包含所有连通顶点和边（无向图） 弱连通图 有向图的基图（忽略方向）连通

有向图带方向不连通，去掉方向才连通，则是弱连通 强连通⇒弱连通，反之不成立 完全图 无向：$n(n-1)/2$边
有向：$n(n-1)$边 边数达到理论最大值 拓扑序列 有向无环图的线性序列（u→v则u在前） 存在拓扑序⇔无环；若有向图中存在拓扑序列，则该图没有回路

二、存储结构对比

结构 空间复杂度 适用场景 优缺点 邻接矩阵 O(n²) 稠密图/频繁判断边 优点：随机访问快
缺点：稀疏图浪费空间 邻接表 O(n+e) 稀疏图/遍历操作 优点：节省空间
缺点：判断两顶点是否相邻效率低 十字链表 O(n+e) 有向图 同时存储入边和出边 邻接多重表 O(n+e) 无向图 删除边操作高效

三、关键算法分析

1. 遍历算法对比

算法 数据结构 时间复杂度 应用场景 特殊性质 BFS 队列 O(n+e) 无权图最短路径（例题9） 按层遍历 DFS 栈/递归 O(n+e) 拓扑排序、强连通分量 递归退出顺序=逆拓扑序（例题6）

2. 拓扑排序实现

void TopologicalSort(Graph G) {  // 1. 计算各顶点入度 // 2. 将入度为0的顶点入队 while (!QueueEmpty(Q)) {  v = DeQueue(Q); print(v); for (w : v的邻接点) {  if (--indegree[w] == 0) EnQueue(Q, w); } }}

• 关键说明：
  • 存在拓扑序⇔无环
  • 邻接矩阵存有向图，则该图拓扑序列：存在，可能不唯一。

四、图的性质定理

1. 度与边数e关系

图类型 公式 推论 无向图 $\sum deg(v)=2e$ 奇度顶点必有偶数个 有向图 ∑deg+(v)=e\\sum deg^+(v) = e∑deg+