chapter9: 图论
基本概念
对于图G(V,E),V(vertices)被称为“顶点集合”，E则是“边集合”，存在两种图，一种是无向图(A - B，朋友关系)，另一种是有向图(A -> B, 课程先修关系)
连通(connected)
无向图 (Undirected Graph)
- 连通 (Connected)：两个顶点之间存在路径。
- 连通图 (Connected Graph)：任意两个顶点都连通。
- 连通分量 (Connected Component)：最大连通子图。
例子：
A —— B —— C D —— E
有向图 (Directed Graph)
- 强连通 (Strongly Connected)
- 任意两个顶点 A、B，都存在从 A 到 B 的有向路径，同时也存在从 B 到 A 的有向路径。
- 弱连通 (Weakly Connected)
- 如果忽略边的方向，把有向图当作无向图后是连通的，那么这个有向图就是弱连通。
- 强连通分量 (Strongly Connected Component)
- 有向图中最大的强连通子图。
- 类似于无向图的连通分量，只是要求更严格：必须双向可达。
小结
- 无向图只有 连通 (Connected) 和 连通分量 (Connected Component)。
- 有向图有 强连通 (Strongly Connected)、弱连通 (Weakly Connected)，以及 强连通分量 (Strongly Connected Component)。
有向无环图 (DAG)
不存在A->B->C->A这种关系的有向图
拓扑排序(Topological Order)
定义与理解
- 拓扑排序就是满足依赖关系的线性排序，我们只要让在图中的后驱排在其前驱的后面即可，因此有不唯一的拓扑排序
Example
对于关系:
c1->c2,
c2->c3->c7,
c8->c9
c1,c2->c3->c7,c8->c9，也可以是c1->c2, c3, c8, c7, c9,一个是分层写法，依赖关系更直接，一个是线性写法，也没问题
算法
前置概念
-
入度 (Indegree) 表示有多少条边直接指向某个顶点。
-
计算入度 (Indegree Array)
-
对每个顶点，统计有多少条边指向它。
-
初始化队列 (Queue)
-
把所有入度为 0 的顶点放入队列。
-
循环处理
- 从队列取出一个顶点，输出它。
- 删除它的边，更新后继顶点的入度。
-
如果某个顶点入度变成 0，就加入队列。
-
结束条件
- 队列为空时结束。
- 如果输出的顶点数 < 总顶点数，说明图里有环 (Cycle)，拓扑排序失败。
Example
关系：
A → B → C
A → D
- 初始入度：A=0, B=1, C=1, D=1
- 队列：{A}
- 输出 A → 更新 B=0, D=0 → 队列 {B,D}
- 输出 B → 更新 C=0 → 队列 {D,C}
- 输出 D → 队列 {C}
- 输出 C → 队列空 → 结束
结果：
A, B, D, C
复杂度对比
-
朴素方法 (Naive Method)
- 思路：每次都要扫描所有顶点，找一个入度为 0 的顶点。
- 每次删除一个顶点后，还要重新计算其他顶点的入度。
- 时间复杂度：
- 外层循环要执行 \(|V|\) 次。
- 每次扫描需要 \(|V|\) 的时间。
- 总复杂度：\(O(|V|^2)\)。
-
队列方法 (Queue Method)
- 思路：
- 一开始就把所有入度为 0 的顶点放进队列。
- 每次取出一个顶点，只更新它的后继顶点的入度。
- 每条边只会被处理一次。
- 时间复杂度：
- 处理所有顶点：\(O(|V|)\)。
- 处理所有边：\(O(|E|)\)。
- 总复杂度：\(O(|V|+|E|)\)。
- 思路：
Dijkstra algorithm
- 主要用于求单源最小路径，基本要求是 不能出现负权边
思路
- 首先确定起点a，然后
dist[a] = 0,其余dist[x] = ∞ - 找到a的邻居(有向图中注意方向性)，计算
dist[邻居点] = min(之前的数据(对于第一组来说一定是∞)， 边的权重和) - 然后找到a的邻居中dist最小的顶点，他的最小距离就被定死了(没有负权边)，从这个定死的点出发找他的邻居，计算
min[xx] = min(之前的数据， 边的权重+这个最小邻居的距离),一直顺推下去。