6 图
6.1 基本定义
- 图: 图(graph) 是由两个集合 V 和 E 组成。 V 是顶点的有穷非空集合， E 是 V 中顶点偶对(边)D的有穷集合
- 无向完全图：具有 n(n-1)/2 条边，则为无向完全图
- 有向完全图: n(n-1) 条边，则为有向完全图
- 度：顶点 V 相关联的边的数目
- 入度(有向)：以顶点 V 为头的弧的数目
- 出度(有向)：以顶点 V 为尾的弧的数目
- 路径和路径长度: 从顶点 V 到 顶点 S 的一系列边为路径，路径长度为边 / 弧的数目
- 回路或环：第一个顶点到最后一个顶点相同的路径称为回路或环
- 简单路径：序列中顶点不重复出现的路径称为简单路径
- 简单回路(简单环)：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
- 连通：在无向图 G 中，从顶点 V 到顶点 S 有路径，则称 V 和 S 是连通的
- 连通图：如果图中任意两个顶点都连通，则称为连通图
- 连通分量：无向图中的极大连通子图
- 强连通分量：有向图中极大强连通子图称为强连通分量
- 强连通图：对每一对 Vi，Vj，从 Vi 到 Vj 和从 Vj 和 Vi 都存在路径，则G为强连通图
6.2 图的表示方法
6.2.1 邻接矩阵
邻接矩阵：是表示顶点之间相邻关系的矩阵，设 G(V, E) 是具有n个顶点的图，则 G 的邻接矩阵具有如下性质
A[i][j] = 1 存在边, 0 则不存在邻接矩阵是一个二维数组，通过 ij 代表两个顶点的边，所有二维数组对角线全为0，若在有向图中，行为出度，列为入度
6.2.2 邻接表
- 无向图结点
typedef struct node {
int data,
struct node * next;
}
- 有向图节点
typedef struct node {
int data,
// 出度
struct node *next;
// 入度
struct node *prev;
}
6.3 最小生成树
6.3.1 普里姆(Prim)算法
选择一条权值最小的边，从权值最下边入度的结点相邻结点边中选最小边，直到完成
6.3.2 克鲁斯卡尔(Kruskal)算法
选择两个结点，其边权值最小。重复完成
6.3.3 最短路径
6.3.3.1 迪杰斯特拉算法
求解过程
对于有向图，分为两组：已求出最短路径的重点集合，尚未求出最短路径终点集合
| 源点 | 终点 | 最短路径 | 路径长度 |
|---|---|---|---|
| v0 | v2 | (v0, v2) | 10 |
| v0 | v4 | (v0, v4) | 30 |
| v0 | v3 | (v0, v4, v3) | 50 |
| v0 | v5 | (v0, v4, v3, v5) | 60 |
| v0 | v1 | – | – |
根据算法，先求出源点及源点相邻节点的路径，并记录下来。
依次进行扩展，若扩展过程中，原有路径大于扩展路径，并更新。类似于计网的路由
6.3.3.2 弗洛伊德算法
将 Vi 到 Vj 的最短路径长度初始化，然后每次在两者之间加入顶点 V0，比较(Vi, Vj) 和 (Vi, V0, Vj) 的路径长度，
取其较短者作为 Vi 到 Vj 的中间顶点的最短路径(寻找相邻结点最短结点)
6.4 拓扑排序
在有向图中选一个无前驱的顶点且数除，从图中删除该顶点和所有以它为尾的弧，继续重复，直到不存在前驱顶点。
6.5 AOE 网(关键路径)
AOV 相对应的就是 AOE 网。即以边表示活动的网。AOE 是一个带权的有向无环图。顶点表示事件，弧表活动，权表活动持续时间。
- 事件最早发生时间
进入事件 Vi 的每一个活动都结束，Vi 才可以发生。 Ve(0) = 0, Ve(i) = Max{Ve(k) + w_{k,i}}
- 事件最迟发生时间
事件 Vi 发生不得延误 Vi的每一后继事件的最迟发生时间。
Vi 的最迟发生时间不得迟于其后继事件 V_k 的最迟发生事件减去活动<V_i, V_k>的持续时间
Vl(i) = Min{Vl(k) – w_{i,k}}
- 活动最早开始时间
只有事件 Vj 发生了，活动 ai 才能开始。所以活动 ai 的最早事件等于事件 Vj 的最早发生时间: e(i) Ve(j)
- 活动最晚开始时间
活动 ai 的开始时间需保证不延误事件 Vk 的最迟发生事件。所以活动 ai 的最晚开始时间 l(i) 等于时间 Vk 的最迟发生时间
Vl(k) 减去活动 ai 的持续时间 w_{j,k}: l(i) = Vl(k) – w-{j, k}
最早发生时间: ve(i)
ve(0) = 0
ve(1) = Max{ve(0) + w0,1} = 6
ve(2) = Max{ve(0) + w0,2} = 4
ve(3) = Max{ve(0) + w0,3} = 5
ve(4) = Max{ve(1) + w1,4, ve(2)+w2,4} =7
ve(5) = Max{ve(3) + w3,5} = 7
ve(6) = Max{ve(4) + w4,6} = 16
ve(7) = Max{ve(4) + w4,7, ve(5)+w5,7} = 14
ve(8) = Max{ve(6) + w6,8, ve(7)+w7,8} = 18
最迟发生时间vl(i)
vl(8) = ve(8) = 18
vl(7) = Min{vl(8) - w7,8} = 14
vl(6) = Min{vl(8) - w6,8} = 16
vl(5) = Min{vl(7) - w5,7} = 10
vl(4) = Min{vl(6) - w4,6, vl(7) - w4,7} = 7
vl(3) = Min{vl(5) - w3,5} = 8
vl(2) = Min{vl(4) - w2,4} = 6
vl(1) = Min{vl(4) - w1,4} = 6
vl(0) = Min{vl(1) - w0,1, vl(2) - w0,2, vl(3) - w0,3} = 0
活动最早时间 e(i) e(a1) = ve(0) = 0 e(a2) = ve(0) = 0 e(a3) = ve(0) = 0; e(a4) = ve(1) = 6; e(a5) = ve(2) = 4; e(a6) = ve(3) = 5; e(a7) = ve(4) = 7; e(a8) = ve(4) = 7; e(a9) = ve(5) = 7; e(a10) = ve(6) = 16; e(a11) = ve(7) = 14;
活动最迟开始时间 l(i) l(a11) = vl(8) - w7,8 = 14 l(a10) = vl(8) - w6,8 = 16 l(a9) = vl(7) - w5,7 = 10 l(a8) = vl(7) - w4,7 = 7 l(a7) = vl(6) - w4,6 = 7 l(a6) = vl(5) - w3,5 = 8 l(a5) = vl(4) - w2,4 = 6 l(a4) = vl(4) - w1,4 = 6 l(a3) = vl(3) - w0,3 = 3 l(a2) = vl(2) - w0,2 = 2 l(a1) = vl(1) - w0,1 = 0
邻接矩阵和邻接表的比较
| 项目 | 邻接矩阵 | 邻接矩阵 | 邻接表 | 邻接表 |
|---|---|---|---|---|
| – | 无向图 | 有向图 | 无向图 | 有向图 |
| 顶点表节点个数 | n | n | n | n |
| 边节点个数 | 邻接矩阵堆成可压缩到 n^2 / 2 | n^2 | 2e | e |
| 求某个顶点 v1 的度 | 扫描邻接矩阵中序号i对应的行 O(1) | 求出度：扫描邻接矩阵的一行 O(n). 求入度：扫描矩阵的一列 | 扫描 vi 的边表，最坏O(n) | 求出度：扫描vi的边表最坏O(n)。入度：按顶点表顺序扫描所有边表O(n+e) |
| 求边的数目 | 扫描邻接矩阵O(n^2) | 扫描邻接矩阵O(n^2) | 按顶点表舒徐扫描所有边表，O(n+2e) | 按顶点表顺序扫描所有边表O(n+e) |
| 判定边 （vi, vj) 是否存在 | 直接检查邻接矩阵A[i][j]元素的值 | 直接检查邻接矩阵A[i][j]元素的值 | 扫描Vi的边表，最坏情况O(n) | 扫描Vi的边表，最坏情况O(n) |
125jz网原创文章。发布者：江山如画，转载请注明出处：http://www.125jz.com/8814.html
微信扫一扫 
支付宝扫一扫