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

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)