【数据结构C++之看懂就这一篇】图（下）

📚博客主页：Zhui_Yi_
🔍：上期回顾：图【中】

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻，您的三连就是我持续更新的动力❤️
🎇追当今朝天骄，忆顾往昔豪杰。

前言

本期我将带来图的应用，包括最小生成树、最短路径、拓扑排序、关键路径。

一、最小生成树

引入以及复习

在理解最小生成树的时候，我们先了解一下生成树。

生成树：包含图G所有顶点的极小连通子图（n-1条边）。

那么什么是极小连通子图呢？

极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。

广度优先生成树和深度优先生成树

那么我们上篇文章提到了广度优先遍历和深度优先遍历：
在广度优先遍历和深度优先遍历过程中，可以得到一颗遍历树，我们称之为广度优先生成树和深度优先生成树。

那么我们根据这个图，以v0作为起点，画出生成树。
我们先把邻接表给画出来：

那么画出来深度优先生成树如下：

广度优先生成树如下：

求最小生成树

我们首先明确一下：

使用不同的遍历图的方法，可以得到不同的生成树
从不同的顶点出发，也可能得到不同的生成树。
按照生成树的定义，n 个顶点的连通网络的生成树有n 个顶点、n-1 条边。

那么我们该如何求最小生成树？

在网的多个生成树中，寻找一个各边权值之和最小的生成树

构造最小生成树的准则：

必须只使用该网中的边来构造最小生成树；
必须使用且仅使用n-1条边来联结网络中的n个顶点
不能使用产生回路的边

那么最小生成树有什么用途呢？

欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n–1条线路，使总费用最少？

如何求最小生成树

在这里有两种求法：

Prim（普里姆）算法
Kruskal（克鲁斯卡尔）算法

他们的特点是：

Prim算法: 归并顶点，与边数无关，适于稠密网
Kruskal算法：归并边，适于稀疏网

Prim算法

基本思想：归并顶点

设连通网络 N = { V, E }中找最小生成树T={V，TE}

1. 从某顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中
2. 每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到U中
3. 直到所有顶点都加入到生成树顶点集合U中为止

应用构造最小生成树的过程

我们先把A结点放在U里面，再把其他节点放在V-U里面

然后再找与A相连权值最小的，AB,AC,AD,AE，谁权值最小？AB，再把B放在U里面

然后再找与U里面的结点相连权值最小的：AC,AD,AE,BC，谁权值最小？
BC，再把C放在U里面

然后再找最小的，AD,AE,CD,CE，谁最小？
AD，把D放在U里面

最后就是DE

接下来我们考虑几个问题：
如果AE=DE=6，我们该选择那条边呢？
都可以，那么从这里我们得到了什么？
最小生成树的形态不唯一。
那么什么是唯一的呢？
最小生成树的权值之和！！！
如何区分点在U还是在V-U集合？
标志变量！！！
这里我们试一下：

画出最小生成树：
先建立邻接矩阵

我们在建立一个一维数组

其中最开始的时候U中只有0，故：

然后再比较谁最小，5，故：

此时U中有0和5，故：

不断重复以上操作：

kruscal算法

克鲁斯卡尔算法的基本思想－归并边

设连通网络 N = { V, E }中找最小生成树T={V，TE}

1. 构造一个只有 n 个顶点，没有边的非连通图 TE= { V,  }, 每个顶点自成一个连通分量
2. 在 E 中选最小权值的边,若该边的两个顶点落在不同的连通分量上，则加入 TE 中；否则舍去，重新选择
3. 重复下去，直到所有顶点在同一连通分量上为止

实现该算法的关键为如何避免选取的边构成回路

➢假设存在n个顶点，设置一t个辅助数组vset[0…n-1] ➢数据元素vset[i] (初值为i)代表编号为i的顶点所属的连通子图编号
➢如果边(i, j)的两个顶点vset[i]== vset[j],不选，否则选取
➢一旦选取(i,j)将两个顶点的连通分量的vset值改为vset[i]或vset[j]

构造上述的最小生成树：

首先按权值大小分：

然后再设置辅助元素的值：

首先选择权值最小的AB，A和B能连嘛？
A的值为0，B的值为1，不一样，可以选，同时使两个顶点的值相同：

然后在选取权值最小的，BC，能选吗？
值不相同，可以，再改变C的值使他们相等：

然后再看谁权值最小，AC，能选吗？
不能，A和C的值都为0。再往下看：
AD，能选吗？
值不相同，能选，再改值：

重复上述操作：

二、最短路径

典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？
问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

特别注意，最短路径跟最小生成树是不一样的。最短路径上不一定包含n个顶点。

两种常见的最短路径问题：
一、 单源最短路径—用Dijkstra（迪杰斯特拉）算法
二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法

Dijkstra算法

Dijkstra算法的思想–按路径长度递增次序求解：

1.初始化：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。
2.选择：从这些路径中找出一条长度最短的路径（v0,u）。
3.更新：然后对其余各条路径进行适当调整：
若在图中存在弧（u,vk），且（v0,u）+（u,vk）<（v0,vk）,
则以路径（v0,u,vk）代替（v0,vk）。
在调整后的各条路径中，再找长度最短的路径，依此类推。

如图。

然后建立表格

存储结构（顶点个数为n）

主：邻接矩阵G[n][n] (或者邻接表)
辅：
数组S[n]：记录相应顶点是否已被确定最短距离
数组D[n]：记录源点到相应顶点路径长度
数组Path[n]：记录相应顶点的前驱顶点

初始化结果如图

算法思想

① 初始化：
● 将源点v0加到S中，即S[v0] = true；
● 将v0到各个终点的最短路径长度初始化为权值，即D[i] = G.arcs[v0][vi]，(vi∈V − S)；
● 如果v0和顶点vi之间有弧，则将vi的前驱置为v0，即Path[i] = v0，否则Path[i] = −1。
② 选择下一条最短路径的终点vk，使得：
D[k] = Min{D[i]|vi∈V − S}
③ 将vk加到S中，即S[vk] = true。
④ 更新从v0出发到集合V − S上任一顶点的最短路径的长度，同时更改vi的前驱为vk。
若S[i]=false 且 D[k]+G.arcs[k][i]<D[i]，则D[i]=D[k]+ G.arcs[k][i]; Path [i]=k;。
⑤ 重复②～④ n − 1次，即可按照路径长度的递增顺序，逐个求得从v0到图上其余各顶点的最短路径。

如图

这是我给出一个例子：

算法流程图如下：

代码实现如下：

void ShortestPath_DIJ(AMGraph G, int v0){ 
    //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 
    n=G.vexnum;                    		//n为G中顶点的个数 
    for(v = 0; v<n; ++v){             	//n个顶点依次初始化 
       S[v] = false;                  	//S初始为空集 
       D[v] = G.arcs[v0][v];           	//将v0到各个终点的最短路径长度初始化 
       if(D[v]< MaxInt)  Path [v]=v0; //v0和v之间有弧，将v的前驱置为v0 
       else Path [v]=-1;               	//如果v0和v之间无弧，则将v的前驱置为-1 
      }//for 
      S[v0]=true;                    	//将v0加入S 
      D[v0]=0;                      		//源点到源点的距离为0 
      /*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集―*/ 
      for(i=1;i<n; ++i){               	//对其余n−1个顶点，依次进行计算 
        min= MaxInt; 
        for(w=0;w<n; ++w) 
          if(!S[w]&&D[w]<min)  
              {v=w; min=D[w];}         	//选择一条当前的最短路径，终点为v 
        S[v]=true;                   		//将v加入S 
        for(w=0;w<n; ++w) 	//更新从v0出发到集合V−S上所有顶点的最短路径长度 
        if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){ 
             D[w]=D[v]+G.arcs[v][w];   	//更新D[w] 
             Path [w]=v;              		//更改w的前驱为v 
        }//if 
    }//for       
}//ShortestPath_DIJ 

时间复杂度为：O(n2)

三、拓扑排序

引入

用有向图来描述一个工程或系统的进行过程。
一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成。

① AOV网(Activity On Vertices)—用顶点表示活动的网络
② AOE网(Activity On Edges)—用边表示活动的网络

比如教学计划的制定
哪些课程是必须先修的，哪些课程是可以并行学习的。

AOV网

用顶点表示活动，用边表示活动间的优先关系。

如图。

AOE网

用顶点表示事件，用边表示活动，权表示活动持续的时间。通常可用来估算工程的完成时间。

如图。

AOV网示例

如图
应该这样画。

算法思想（重复选择没有直接前驱的顶点）

1.输入AOV网络。令 n 为顶点个数。
2.在AOV网络中选一个没有直接前驱的顶点, 并输出之;
3.从图中删去该顶点, 同时删去所有它发出的有向边;
4.重复以上 2、3 步, 直到：
全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或：
图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。

总结

本篇文章有点粗造，抱歉各位，状态不是很好。
希望可以三哈！！！