408数据结构学习笔记——图的应用

目录 1.最小生成树 1.1.最小生成树的概念 1.2.Prim算法 1.3.Kruskal算法（库鲁斯卡尔） 2.最短路径 2.1.BFS 2.2
2023-11-24 技术

目录

1.最小生成树

1.1.最小生成树的概念

1.2.Prim算法

1.3.Kruskal算法（库鲁斯卡尔）

2.最短路径

2.1.BFS

2.2.Dijkstra算法

2.2.1.Dijkstra算法的基本概念

2.2.2.Dijkstra的时间复杂度

2.2.3.Dijkstra的不适用情况

2.3.Floyd算法

2.3.1.Floyd算法的基本概念

2.3.2.Floyd算法的复杂度

2.4.最短路径小结

3.有向无环图

3.1.描述表达式

3.2.拓扑排序 

3.2.1.拓扑排序的概念

3.2.2.拓扑排序的实现

3.2.3.逆拓扑排序

3.3.关键路径

3.3.1.AOE网的性质

3.3.2.AOE网的基本概念

3.3.3.求关键路径的步骤

4.王道课后题​编辑

1.最小生成树

1.1.最小生成树的概念

  1. 边的权值之和最小的生成树，称为最小生成树
  2. 最小生成树不唯一
  3. 连通图本身就是一棵树，则它就是最小生成树
  4. 最小生成树需连通图，非连通图只能是生成森林

1.2.Prim算法

从某一个顶点开始构建最小生成树，依次加入当前剩余顶点中代价最小的顶点，直到加入所有顶点

时间复杂度：O(|V^{2}|)

适用：稠密图（E大）

每一轮开始都循环遍历所有节点，找到当前代价最低且并没有加入树的结点，再次遍历，更新各个结点的代价

1.3.Kruskal算法（库鲁斯卡尔）

每次选择代价最小的一条边，使该边的两个顶点相通，但是，如果原本就相通的两个顶点的边就不选，直到所有顶点相通

时间复杂度：O(|E|log_{2}^{}|E|)

适用：稀疏图（E小）

共执行e轮，每轮判断两个结点是否属于同一个结点

2.最短路径

2.1.BFS

BFS能求无权图的单源最短路径：用额外两个数组分别存储该顶点的前驱和距离源顶点的距离

#define MaxVertexNum 100void BFS(Graph G, int v){Queue Q;InitQueue(Q);EnQueue(v);int q, p;//dist数组用来存放当前顶点到源顶点的距离，pre存放当前顶点的前驱顶点int dist[MaxVertexNum] = { 0 }, pre[MaxVertexNum] = { 0 };bool visited[MaxVertexNum] = { false };//源顶点的前驱置为-1pre[v] = -1;//源顶点标记已访问visited[v] = true;//cur标记当前距离顶点的距离int cur = 0;while(!IsEmpty(Q)){DeQueue(Q, p);cur++;for (q = FirstNeighbor(G, p); q >= 0; q = NextNeighbor(G, p, q)){if (!visited[q]) {//将q设置为已标记visited[q] = true;//入队qEnQueue(Q, p);//更新q距离源顶点的距离dist[q] = cur;//更新q的前驱pre[q] = p;}//if}//for}//while
}

BFS算法求最短路径的局限：仅能求无权图或者各条边权值都相同的图

2.2.Dijkstra算法

2.2.1.Dijkstra算法的基本概念

在求最短路径（单源）的过程中，需要新建四个数组：path（存储到此点路径的上个结点）、dist（距离源点的最短距离）、顶点集S和final（标记是否已经找到最短路径）

第一轮以0为源点，更新以0为起点到各个顶点的数据，如果当前还没有道路能通往该顶点（2，3），则前驱为-1，且距离为 ∞，并把源点0的final标记为已找到

第一轮
S01234
dist010∞∞5
path-10-1-10
final√ ××××

第二轮以当前未找到最短路径且当前路径最低的顶点，即顶点4，将其final改为已找到。以0→4的路径更新各个顶点数据。

第二轮
S01234
dist081475
path-14440
final√ ×××√

第三轮以当前未找到最短路径且当前路径最低的顶点，即顶点1，将其final改为已找到。以0→4→3的路径更新各个顶点数据。

第三轮
S01234
dist081375
path-14340
final√ ×××√

第四轮以当前未找到最短路径且当前路径最低的顶点，即顶点3，将其final改为已找到。以0→4→3→1的路径更新各个顶点数据。

第四轮
S01234
dist08975
path-14140
final√ ××√√

第四轮以当前未找到最短路径且当前路径最低的顶点，即顶点5，将其final改为已找到。

第五轮
S01234
dist08975
path-14140
final√ ××√√

2.2.2.Dijkstra的时间复杂度

每轮都需要遍历两边数组（顶点集），第一遍查找当前距离最短且未被标记的顶点，第二遍更新以该顶点为路径的信息，一共要执行n - 1轮，因此，时间复杂度为O(|V|^{2})，即O(n^{2})（与Prime算法的思想很类似）

2.2.3.Dijkstra的不适用情况

当图中边的权值存在负值时，Dijkstra算法并不适用

2.3.Floyd算法

2.3.1.Floyd算法的基本概念

Floyd算法用于计算有向图/无向图的任意两个结点的最短路径

Floyd算法需要新建两个二维数组，A（保存当前最短路径长度）和path（最短路径的前驱）

初始化A和path数组，不允许任何中转

A
V0V1V2V3V4
V00∞1∞10
V1∞0∞15
V2∞10∞7
V3∞∞∞01
V4∞∞∞∞0
path
V0V1V2V3V4
V0-1-1-1-1-1
V1-1-1-1-1-1
V2-1-1-1-1-1
V3-1-1-1-1-1
V4-1-1-1-1-1

第一轮：允许在V0中转

A
V0V1V2V3V4
V00∞1∞10
V1∞0∞15
V2∞10∞7
V3∞∞∞01
V4∞∞∞∞0
path
V0V1V2V3V4
V0-1-1-1-1-1
V1-1-1-1-1-1
V2-1-1-1-1-1
V3-1-1-1-1-1
V4-1-1-1-1-1

第二轮：允许在V0、V1中转，更新V2→V3、V2→V4

A
V0V1V2V3V4
V00∞1∞10
V1∞0∞15
V2∞1026
V3∞∞∞01
V4∞∞∞∞0
path
V0V1V2V3V4
V0-1-1-1-1-1
V1-1-1-1-1-1
V2-1-1-111
V3-1-1-1-1-1
V4-1-1-1-1-1

第三轮：允许在V0、V1、V2中转，更新V0→V1、V0→V4、V0→V3

A
V0V1V2V3V4
V002138
V1∞0∞15
V2∞1026
V3∞∞∞01
V4∞∞∞∞0
path
V0V1V2V3V4
V0-12-122
V1-1-1-1-1-1
V2-1-1-111
V3-1-1-1-1-1
V4-1-1-1-1-1

第四轮：允许在V0、V1、V2、V3中转，更新V0→V4、V1→V4、V2→V4

A
V0V1V2V3V4
V002134
V1∞0∞12
V2∞1023
V3∞∞∞01
V4∞∞∞∞0
path
V0V1V2V3V4
V0-12-123
V1-1-1-1-13
V2-1-1-113
V3-1-1-1-1-1
V4-1-1-1-1-1

第五轮：允许在V0、V1、V2、V3中转

A
V0V1V2V3V4
V002134
V1∞0∞12
V2∞1023
V3∞∞∞01
V4∞∞∞∞0
path
V0V1V2V3V4
V0-12-123
V1-1-1-1-13
V2-1-1-113
V3-1-1-1-1-1
V4-1-1-1-1-1

2.3.2.Floyd算法的复杂度

空间复杂度：创建两个二维数组O(n2)

时间复杂度：三个for循环O(n3)

2.4.最短路径小结

  1. 无权图：BFS、Dijkstra算法、Floyd算法
  2. 带权图：Dijkstra算法、Floyd算法
  3. 带负权值图：Floyd算法
  4. 带负权值回路图：无
  5. 时间复杂度：
    1. BFS：O(|V^2|)（邻接矩阵）或者O(|V|+|E|)（邻接表）
    2. Dijkstra：O(|V^|2)
    3. Floyd：O(|V|^3)
  6. 通常应用场景：
    1. BFS：无权图单源最短路径
    2. Dijkstra：有权图单源最短路径（也可以求任意两点路径，重复V次，O(|V|^3）
    3. Floyd：有权图各个顶点间最短路径

3.有向无环图

3.1.描述表达式

有向无环图：有向图中不存在回路（DAG图）

解题方法：

  1. 为算式中每一个运算符依次附上编号（运算符的运算顺序）
  2. 按顺序加入运算符和操作数（注意分层）

第一步：初始化，为每个运算符按运算顺序附上编号，并且每个操作数顺序排好

第二步： 将①加入表中

第三步：将②加入表中

第三步：将说③加入表中，注意：③所依靠的运算顺序是先得求出c + d的值，因此，③以②为基础，在②的上一层 

第四步：将④加入表中，④以③为基础，在③的上一层

第五步：将⑤加入表中

第六步：将⑥加入表中，⑥以⑤为基础，⑥在上一层

第七步：将七加入表中，⑦以④、⑥为基础，因此，应该在④、⑥的层高最大值的上一层

第八步：将⑧加入表中

第九步：⑨基于⑦和⑨，并放在⑦的上一层，结束

第十步：合并，检查同一层的运算符是否可以合体

第二层的最后两个*都是指向的cd，因此，可以合并为一个

3.2.拓扑排序 

3.2.1.拓扑排序的概念

  1. 每个顶点出现切仅出现一次
  2. 不存在回路
  3. 每个AOV网都存在一个或多个拓扑排序

3.2.2.拓扑排序的实现

  1. 从AOV网中选择一个没有前驱的顶点输出
  2. 在AOV网中删除该顶点和所有以它为起点的顶点
  3. 重复1、2直到AOV网中没有顶点

3.2.3.逆拓扑排序

每次删除的是出度为0的顶点

#define MaxVertexNum 100bool visited[MaxVertNum] = {false};void DPS_Init(Graph G){for (int i = 0; i < G.verNum; i++){if (!visited[i]) DFS(G, i);}
}void DFS(Graph G, int v){visited[v] = true;int w;for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w){if (!visited[w]) DFS(G, w);}cout << v << endl;
}

3.3.关键路径

用边表示活动的网络(AOE网)：以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销

3.3.1.AOE网的性质

  1. 只有某顶点的事件完成后，从该顶点出发的各有向边代表的活动才能发生
  2. 只有在进入某顶点的有向边所代表的活动都结束时，该顶点的事件才能发生
  3. AOE网中仅有一个点入度为0，即开始顶点（源点）；仅有一个点出度为0，即结束顶点（汇点）
  4. 源点到汇点的最大路径长度的路径称为关键路径，此条路径上的活动为关键活动

3.3.2.AOE网的基本概念

  1. 事件v_{k}的最早发生时间ve(k)——决定了所有从v_{k}开始的活动能开工的最早时间
  2. 活动a_{i}的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间
  3. 事件v_{k}的最晚发生时间vl(k)——在不推迟整个工程完成的情况下，该事件最晚发生时间
  4. 活动_{}a_{i}的最晚开始时间l(i)——该活动弧的终点所表示的事件的最晚发生时间和该活动所需时间的差值
  5. 活动a_{i}的时间余量d(i) = l(i) - e(i)，表示该活动在不增加整个工程完成时间的情况下，最多可以拖延的时间。特别的，当时间余量为0，即l(i) - e(i) = 0时，该活动为关键活动。
  6. 由关键活动组成的路径是关键路径
  7. 关键活动时间增加，整个工程时间增加
  8. 关键活动时间降低，整个工期时间降低，但是，关键活动的时间降低到一定程度时，关键活动可能会变成非关键活动
  9. 关键路径可能有多条，只提高一条关键路径上的关键活动可能并不能降低整个工程的时间，但是降低所有关键路径上都存在的关键活动一定能降低整个工程的时间

3.3.3.求关键路径的步骤

  1. 求所有事件的最早发生时间ve：取直接指向该它的V的VE（V）+ 此权值，多个取MAX（取决于指向点的所有点的VE）
  2. 求所有事件的最晚发生时间vl：取它直接指向的V的VL（V）- 此权值，多个取MIN（取决于该点指向的所有点的VL）
  3. 求所有活动的最早发生时间e：此边起始的V的VE（V）（直接照抄VE）
  4. 求所有活动的最晚发生时间l：此边终点的VL（V）- 此权值
  5. 求所有活动的时间余量

  1. 求出该图的拓扑序列：V1→V2→V3→V4→V5→V6
  2. 求出该图的逆拓扑序列：V6→V5→V4→V3→V2→V1
  3. 求所有事件的最早发生时间：根据拓扑序列
    1. ve(V1) = 0
    2. ve(V2) = 3
    3. ve(V3) = 2
    4. ve(V4) = 6
    5. ve(V5) = 6
    6. ve(V6) = 8
  4. 求所有事件的最晚发生时间：根据逆拓扑序列
    1. vl(V6) = 8
    2. vl(V5) = 7
    3. vl(V4) = 6
    4. vl(V3) = 2
    5. vl(V2) = 4
    6. vl(V1) = 0
  5. 求所有活动的最早发生时间e：根据所有事件的最早发生时间，e(n) = ve(n)，弧起点的事件最早开始时间
    1. e(a1) = 0
    2. e(a2) = 0
    3. e(a3) = 3
    4. e(a4) = 3
    5. e(a5) = 2
    6. e(a6) = 2
    7. e(a7) = 6
    8. e(a8) = 6
  6. 求所有活动的最晚发生时间l：根据所有事件的最晚发生时间，弧终点的事件最晚开始时间减去这个弧的权值
    1. l(a1) = 1
    2. l(a2) = 0
    3. l(a3) = 4
    4. l(a4) = 4
    5. l(a5) = 2
    6. l(a6) = 5
    7. l(a7) = 6
    8. l(a8) = 7
  7. 求所有活动的时间余量：d(an) = v(an) - e(an)
    1. d(a1) = l(a1) - e(a1) = 1
    2. d(a2) = l(a2) - e(a2) = 0
    3. d(a3) = l(a3) - e(a3) = 1
    4. d(a4) = l(a4) - e(a4) = 1
    5. d(a5) = l(a5) - e(a5) = 0
    6. d(a6) = l(a6) - e(a6) = 3
    7. d(a7) = l(a7) - e(a7) = 0
    8. d(a8) = l(a8) - e(a8) = 1
  8. d(a2)、d(a5)和d(a7) = 0，所以关键活动为a2、a5和a7；由他们组成的路径为关键路径，即v1→v3→v4→v6

4.王道课后题

 1.1→2→3→5→7→4→6

1234567
10336∞∞∞
2∞04∞5∞∞
3∞∞0∞43∞
4∞∞∞0∞5∞
5∞∞∞∞0∞3
6∞∞3∞∞07
7∞∞∞∞∞∞0

2.当一个顶点只有出度没有入度时，它不可能与其它顶点成为一个强连通分量；该图有七个强连通分量

3.1→2→4→6→3→5→7；1→4→2→6→3→5→7

4.prim算法：1→2        1→3        3→6        3→5        5→7        6→4

kruskal算法：1→2        1→3        3→6        5→7        3→5        6→4

  1. 顶点2：1→2        7
  2. 顶点3：1→3        11
  3. 顶点4：1→4        16
  4. 顶点5：1→3→5  18
  5. 顶点6：1→3→6  19

  1. 邻接表
    1. v1→v2→v3→v5
    2. v2→v3→v4
    3. v3→v5→v6
    4. v4→v6
    5. v5→v7
    6. v6→v7→v8
    7. v7→v9
    8. v8→v9
    9. v9→NULL
  2. 16
  3. v1→v3→v5→v7→v9
  4. a2、a6、a9、a12

2.最早发生时间：A0、B0、C3、D3、E2、F3、G6、H6

最晚发生时间：A1、B0、C4、D4、E2、F5、G6、H7

3.关键路径：BEF（通过最晚发生时间减去最早发生时间得到时间余量，时间余量为0组成的路径为关键路径）

最短时间：8

#define MaxVertexNum 100bool visited[MaxVertexNum] = {false};
int temp[MaxVertexNum] = { 0 };
int res[MaxVertexNum] = { 0 };
int maxTime = -1;//DFS函数调用入口
void DFS_Entrance(Grpah G){int time = 0;//循环遍历visited数组for (int i = 0; i < G.verNum; i++){//当前元素未被访问过，则访问当前元素if (!visited[i]) DFS(G, i, time);}int k = 0;//res数组保存拓扑序列for (time = 0; time <= maxTime; time++){for (int i = 0; i < verNum; i++){if (temp[i] == time) res[k++] = temp[i];}}
}void DPS(Graph G, int v, int time){//更改当前元素为true，标记为已访问visited[v] = true;temp[v] = time;//输出当前元素cout << v << endl;int w;//循环遍历其邻接顶点for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){//每执行一次循环，当前层数+1time++;//更新最高的层数if (maxTime < time) maxTime = time;if (!visited[w]) DFS(G, w, time);}
}

 Dijkstra算法能生成一棵生成树，但是并不一定是最小生成树

方法不可行

关键路径为abdf，长度为16

1.AD→DE→EC→BC→AB

2.最小生成树唯一

3.带回路的带权连通图其回路的各条边的权值不同

2.邻接表 Dijkstra

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！

推荐阅读