图(Graph)¶
基础概念¶
- 表示为G(V, E)，其中V是顶点集合，E是边集合
- 有向图(Directed Graph)：边有方向，E中的元素表示为
- 无向图(Undirected Graph)：边无方向，E中的元素表示为(u, v)
- v和u之间有边，则称v和u是邻接的(adjacent)
- v和u之间有一条无向边，则称(v, u) is incident on v and u
- v和u之间有一条有向边(u \(\rightarrow\) v)，则称v is adjacent to u, u is adjacent from v
- 不考虑自环(self loop)和重边(Multiple Edge)
- 完全图(Complete Graph)：任意两个顶点之间都有边
- 子图(Subgraph)：G' = (V', E')是G的子图，当且仅当V'是V的子集，E'是E的子集
- 路径(Path)：顶点序列v1, v2, ..., vk
- 简单路径(Simple Path)：除了起点和终点外，其他顶点不重复
- 路径长度：路径经过边的数量
- 回路(Cycle)：起点和终点相同的路径
- 对于无向图：
- 如果图中任意两个顶点之间都有路径，则称图是连通的(Connected)
- 连通分量(Connected Component)：无向图的极大连通子图
- 对于有向图：
- 强连通(Strongly Connected)：任意两个顶点之间都有路径
- 强连通分量(Strongly Connected Component)：有向图的极大强连通子图
- 弱连通(Weakly Connected)：有向图的基础图（将有向边替换为无向边）是连通的
- DAG(Directed Acyclic Graph)：有向无环图
- 树(Tree)：无向图，连通且无回路
- 度数(Degree)：顶点的度数是与该顶点相关联的边的数量
- 入度(In-Degree)：有向图中指向该顶点的边的数量
- 出度(Out-Degree)：有向图中从该顶点出发的边的数量
- 边的数量 = 所有节点的度数之和 除以2
表示¶
- 邻接矩阵(Adjacency Matrix)：
V 个顶点从0开始编号，构成V x V的矩阵，A[i][j]表示顶点i和j之间是（1）否（0）有边
- 无向图：对称矩阵，且对角元都为 0
- 改进：只存下三角(或上三角)，此时A[i][j]数组索引为
i(i+1)/2+j
- 改进：只存下三角(或上三角)，此时A[i][j]数组索引为
- 有向图：可能为非对称矩阵
- 稠密图(Dense Graph)：边数接近V^2
- 稀疏图(Sparse Graph)：边数接近V（空间需求为\(\Theta\)(\(V^2\))
- 度数：对于无向图，第i行或第i列的和；对于有向图，第i行的和为出度，第i列的和为入度
- 无向图：对称矩阵，且对角元都为 0
- 邻接表(Adjacency List)：每个顶点v有一个链表，存储与v邻接的顶点
- 对于有向图，链表中存储的是出边；如果要遍历入度则需要额外储存一个链表
- 对于无向图，链表中存储的是邻接的顶点，这样会将每个边储存两次
- 优点：节省空间，对于稀疏图更好，空间需求为\(\Theta\)(V+E)
- 带权图/网络(Weighted Graph)：边有权值
- 邻接矩阵：A[i][j]表示顶点i和j之间的权值
- 邻接表：链表中存储的是边的权值
遍历¶
DFS:¶
深度优先——无路可走时回溯
void DFS(int v) {
visited[v] = true;
for (int w = FirstNeighbor(v); w >= 0; w = NextNeighbor(v, w)) {
if (!visited[w]) {
DFS(w);
}
}
}
- 欧拉回路和欧拉路径
- 欧拉回路（Eulerian Cycle）：通过图中每条边一次且仅一次，回到起点
- 欧拉路径（Eulerian Path）：通过图中每条边一次且仅一次，不一定回到起点
- 无向连通图中：
- 所有顶点的度数为偶数：存在欧拉回路
- 有且仅有两个顶点的度数为奇数：存在欧拉路径
- 有向连通图中：
- 弱连通且所有顶点的入度等于出度：存在欧拉回路
- 弱连通且有且仅有一个顶点的入度比出度大1，有且仅有一个顶点的入度比出度小1，其他顶点入度等于出度：存在欧拉路径
BFS¶
广度优先——层层外扩
void BFS(Vertex v) {
visited[v] = true;
Enqueue(v, Q);
while (!IsEmpty(Q)) {
v = Dequeue(Q);
for (int w = FirstNeighbor(v); w >= 0; w = NextNeighbor(v, w)) {
if (!visited[w]) {
visited[w] = true;
Enqueue(w, Q);
}
}
}
}
拓扑排序¶
- AOV 网络：Active on vertex
- 拓扑序：AOV中从V到W有一条有向路径，则V在W之前
- AOV若为合理的拓扑序，则必为有向无环图
- 拓扑排序：对有向无环图进行排序，使得所有边的起点在终点之前
- 有向无环图的拓扑排序不唯一
- 有向无环图的拓扑排序不一定存在
- 拓扑排序算法：
- 从入度为0的顶点开始，每次删除一个顶点和与之关联的边
- 若图中还有顶点，则图中有回路
void TopSort(Graph G) { int cnt = 0; for (int i = 0; i < G->Nv; i++) { if (indegree[i] == 0) { Enqueue(i, Q); // 入度为0的顶点入队 } } while (!IsEmpty(Q)) { v = Dequeue(Q); // 出队 print v; cnt++;// 计数 for (int w = FirstNeighbor(v); w >= 0; w = NextNeighbor(v, w)) { if (--indegree[w] == 0) { // 入度减1同时判断是否为0 Enqueue(w, Q); } } } if (cnt != G->Nv) { printf("图中有回路"); }
最短路径(Shortest Path)¶
在网络中，从一个顶点到另一个顶点的路径中，边的权值之和最小的路径，第一个顶点称为源点(Source)，最后一个顶点称为终点(Destination)
- 单源最短路径问题(Single-Source Shortest Path)：求源点到其他所有顶点的最短路径
- 无权图：经历的顶点最少
- 有权图：边的权值之和最小
- 多源最短路径问题(All-Pairs Shortest Path)：求任意两个顶点之间的最短路径
单源无权图¶
- 按照递增（非递减）的顺序，找出到各顶点的最短路径
- 用BFS实现：从源点开始，每次遍历到的点的路径长度为上一点的路径长度+1
用于无权图的最短路径算法，时间复杂度为O(|V|+|E|)
void Unweighted(Vertex S) { Enqueue(S, Q); while (!IsEmpty(Q)) { V = Dequeue(Q); for (int W = FirstNeighbor(V); W >= 0; W = NextNeighbor(V, W)) { if (dist[W] == -1) { // dist[]初始化为-1, 表示未访问 dist[W] = dist[V] + 1; // 更新路径长度为上一点的路径长度+1 path[W] = V; // 记录路径 Enqueue(W, Q); } } } }for loop实际上只是遍历了所有的边，所以时间复杂度为O(|E|)- 每个顶点入队出队各一次，所以时间复杂度为O(|V|)
单源有权图¶
- 权重代表边的长度
- 边权值可以为负数
- 负值环：环路权值之和为负数
-
Dijkstra算法：按照递增的顺序找出源点到其他所有顶点的最短路径
- 不能处理负权边
- 分为两个集合：未确定最短路的顶点集合T&源点+已确定最短路径的顶点集合S
- 初始化dist[s] = 0, 其他为无穷大
-
重复下面的操作：
- 从T中选择一个顶点V，使得dist[V]最小, 将V加入S
- 对刚刚加入S的节点的所有出边(v,w)执行松弛操作：
dist[w] = min(dist[w], dist[v]+weight(v,w))
-
伪代码描述
时间复杂度取决于如何找到未收录顶点中dist最小者 - 简单实现：每次遍历所有未收录顶点，时间复杂度为O(|V|^2)
- 优化实现：使用最小堆，时间复杂度为O\(((|V|+|E|) \log|V|\))
- 每次取出堆顶元素，时间复杂度为O(log|V|)
- 每个顶点最多入堆出堆一次，时间复杂度为O\((|V| \log|V|)\)
- 每个边最多入堆一次，时间复杂度为O\((|E|\log|V|)\)
网络流(Network Flow)¶
- 网络流定义在一个有向图上，每条边上有一个代表容量(Capacity)的权值，当\((u, v) \in E\)时，\(c(u, v)\)表示从u到v的容量; 当\((v, u) \notin E\)时，定义\(c(v, u) = 0\)
- 网络中存在唯一的源点s（source）和唯一的汇点t(sink)
- 流量：从u到v的流量\(f(u, v)\)，满足以下条件：
- 容量限制：\(0 \leq f(u, v) \leq c(u, v)\)
- 流量守恒：\(\sum_{v \in V} f(u, v) = \sum_{v \in V} f(v, u)\)
- 最大流问题：在网络中从源点到汇点的流量最大化问题
- 建立残差图（residual graph），设 \(f\) 是图 \(G=(V,E)\) 的一个流，则残差图的边权为：
\[ c_f(u,v)=\begin{cases} c(u,v)-f(u,v)\;\;&(u,v)\in E \cr f(v,u)&(v,u)\in E \cr 0&\text{else} \end{cases} \]
-
重复以下操作，直到残差图中不存在增广路径：
- 在残差图中找到一条从s到t的路径
- 计算该路径上的最小容量
- 更新流量和残差图
-
寻找增广路径的方法：
- BFS：时间复杂度为 \(\Omicron(|V||E|^2)\)
- Dinic算法：时间复杂度为 \(\Omicron(|V|^2|E|)\)
最小生成树(Minimum Spanning Tree)¶
- 生成树(Spanning tree)：连通无向图的一个生成子图，且满足：
- 生成：包含原图中所有的顶点
- 树：无环且有V-1条边
- 生成树中任加一条边都会形成环
- 最小生成树(Minimum Spanning Tree)：生成树中边的权值之和最小：
- 连通图一定存在最小生成树，反之亦然；
- 但不一定唯一（如果存在权值相等的边的话）
-
Prim算法：
- 从一个顶点开始，每次找到一个与当前生成树距离最小的顶点加入生成树，且加入后仍然是树
- 重复直到所有顶点都加入生成树
- 时间复杂度：O(\(|V|^2\)) 或 O(\(|E| \log |V|\))
- 适合稠密图
-
Kruskal算法：
- 从所有边中选择权值最小的边，如果加入后不会形成环，则加入生成树
- 重复直到所有顶点都加入生成树
- 时间复杂度：O(\(|E| \log |E|\)) 或 O(\(|E| \log |V|\))
- 可以使用并查集来判断是否形成环
- 建立并查集
- 将边按照权值排序
- 依次加入边，如果边的两个顶点不在同一个集合中，则合并两个集合，否则不加入
- 适合稀疏图
最后更新:
2024年10月2日 14:45:20
创建日期: 2024年4月16日 13:55:18
创建日期: 2024年4月16日 13:55:18