图的全部知识点、考点梳理-数据结构

6 图

6.1 基本定义

1. 图: 图(graph) 是由两个集合 V 和 E 组成。 V 是顶点的有穷非空集合， E 是 V 中顶点偶对(边)D的有穷集合
2. 无向完全图：具有 n(n-1)/2 条边，则为无向完全图
3. 有向完全图: n(n-1) 条边，则为有向完全图
4. 度：顶点 V 相关联的边的数目
5. 入度(有向)：以顶点 V 为头的弧的数目
6. 出度(有向)：以顶点 V 为尾的弧的数目
7. 路径和路径长度: 从顶点 V 到 顶点 S 的一系列边为路径，路径长度为边 / 弧的数目
8. 回路或环：第一个顶点到最后一个顶点相同的路径称为回路或环
9. 简单路径：序列中顶点不重复出现的路径称为简单路径
10. 简单回路(简单环)：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
11. 连通：在无向图 G 中，从顶点 V 到顶点 S 有路径，则称 V 和 S 是连通的
12. 连通图：如果图中任意两个顶点都连通，则称为连通图
13. 连通分量：无向图中的极大连通子图
14. 强连通分量：有向图中极大强连通子图称为强连通分量
15. 强连通图：对每一对 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 邻接表

1. 无向图结点

typedef struct node {
    int data,
    struct node * next;
}

2. 有向图节点

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 迪杰斯特拉算法

求解过程

对于有向图，分为两组：已求出最短路径的重点集合，尚未求出最短路径终点集合

根据算法，先求出源点及源点相邻节点的路径，并记录下来。
依次进行扩展，若扩展过程中，原有路径大于扩展路径，并更新。类似于计网的路由

6.3.3.2 弗洛伊德算法

将 Vi 到 Vj 的最短路径长度初始化，然后每次在两者之间加入顶点 V0，比较(Vi, Vj) 和 (Vi, V0, Vj) 的路径长度，
取其较短者作为 Vi 到 Vj 的中间顶点的最短路径(寻找相邻结点最短结点)

6.4 拓扑排序

在有向图中选一个无前驱的顶点且数除，从图中删除该顶点和所有以它为尾的弧，继续重复，直到不存在前驱顶点。

6.5 AOE 网(关键路径)

AOV 相对应的就是 AOE 网。即以边表示活动的网。AOE 是一个带权的有向无环图。顶点表示事件，弧表活动，权表活动持续时间。

1. 事件最早发生时间

进入事件 Vi 的每一个活动都结束，Vi 才可以发生。 Ve(0) = 0, Ve(i) = Max{Ve(k) + w_{k,i}wk,i​}

2. 事件最迟发生时间

事件 Vi 发生不得延误 Vi的每一后继事件的最迟发生时间。
Vi 的最迟发生时间不得迟于其后继事件 V_k 的最迟发生事件减去活动<V_iVi​, V_kVk​>的持续时间
Vl(i) = Min{Vl(k) – w_{i,k}wi,k​}

3. 活动最早开始时间

只有事件 Vj 发生了，活动 ai 才能开始。所以活动 ai 的最早事件等于事件 Vj 的最早发生时间: e(i) Ve(j)

4. 活动最晚开始时间

活动 ai 的开始时间需保证不延误事件 Vk 的最迟发生事件。所以活动 ai 的最晚开始时间 l(i) 等于时间 Vk 的最迟发生时间
Vl(k) 减去活动 ai 的持续时间 w_{j,k}wj,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

邻接矩阵和邻接表的比较