【数据结构】图的应用（普利姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、拓扑排序）

末蓝、 2024-04-17 06:00 25阅读 0赞

## 最小生成树 ##

#### 什么是最小生成树 ####

*  是一棵**树**  
    \- 无回路  
    \- |V|个顶点一定有|V|-1条边
 *  是**生成**树  
    \- 包含全部顶点  
    \- |V|-1条边全在图里

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

### 贪心算法 ###

什么是“贪”：每一步都要最好的  
什么是“好”：权重最小的边  
需要约束：

1.  只能用图里有的边
2.  只能正好用掉|V|-1条边
3.  不能有回路  
    ![在这里插入图片描述][20190826103821658.png]

### 普利姆（Prim）算法——让一棵小树长大 ###

需要维护两个数组：`lowcost[n] 、adjvex[n]`（n是图中的顶点数）  
①从图中找第一个起始顶点v0，作为生成树的第一个顶点，然后从这个顶点到其他顶点的所有边中选一条**权值最小**的边。然后把这条边的另一个**顶点v**和这条边加入到生成树中。  
②对剩下的其他所有顶点，分别检查这些顶点与**顶点v**的权值是否比这些顶点在lowcost数组中对应的权值小，如果更小，则用较小的权值更新lowcost数组。  
③从更新后的lowcost数组中继续挑选权值最小**而且不在生成树**中的边，然后加入到生成树。  
④反复执行②③直到所有**所有顶点**都加入到生成树中。  
[视频讲解][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]

Void MiniSpanTree_Prim(MGraph G){
           int min,i,j,k;
           int adjvex[MAXVEX];   //保存邻接顶点下标的数组
           int lowcost[MAXVEX]; //记录当前生成树到剩余顶点的最小权值
           lowcost[0]=0;             //将0号顶点(以0号顶点作为第一个顶点)加入生成树
           adjvex[0]=0;               //由于刚开始生成树只有一个顶点 不存在边 干脆都设为0
           for(i=1;i<G.vexnum;i++){ //除下标为0以外的所有顶点
                     lowcost[i]=G.arc[0][i];   //将与下标为0的顶点有边的权值存入Lowcost数组
                     adjvex[i]=0;                 //这些顶点的adjvex数组全部初始化为0
           }
           //算法核心
           for(i=1;i<G.vexnum;i++){//只需要循环N-1次，N为顶点数
                      min=65535; //tip：因为要找最小值，不妨先设取一个最大的值来比较
                      j=0;k=0;
                      //找出lowcost最小的 最小权值给min，下标给k
                      while(j<G.vexnum){ //从1号顶点开始找
                                if(lowcost[j]!=0 && lowcost[j]<min){ //不在生成树中的顶点而且权值更小的
                                         min=lowcost[j]; //更新更小的值
                                         k=j;  //找到了新的点下标给k
                                 }
                                 j++; //再看下一个顶点
                      }
                      printf(“(%d->%d)”,adjvex[k],k); //打印权值最小的边
                      lowcost[k]=0;  //将这个顶点加入生成树
                       //生成树加入了新的顶点 从下标为1的顶点开始更新lowcost数组值
                      for(j=0;j<G.vexnum;j++){ 
                             if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j]){  //如果新加入树的顶点k使得权值变小
                                       lowcost[j]=G.arc[k][j]; //更新更小的权值
                                       adjvex[j]=k; //修改这条边邻接的顶点 也就是表示这条边是
                                                             从选出的顶点k指过来的  方便打印     
                             }
                      }
            }
    }

#### 算法分析 ####

普利姆算法是双重循环，外层循环次数为n-1，内层并列的两个循环次数都是n。故普利姆算法时间复杂度为O(n2)  
而且时间复杂度只和n有关，所以适合稠密图

### 克鲁斯卡尔（Kruskal）算法——把森林合并成树 ###

我们知道生成树是包含n个顶点，n-1条边的  
换一种思路，我们可以从网中的边这个角度，找最小权值的边，直到找到n-1条边。

#### 思路 ####

将图中边按照权值从小到大**排列**，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入**不构成回路**的话，则将该边并入当前生成树。直到所有的边都检测完为止。

排列： 请参考→ [堆][Link 2]  
不构成回路：请参考→ [并查集][Link 3]

#define MaxSize 100
    typedef struct {
            int a,b;  	//边的两个顶点
            int weight; //边的权值
    }Edge; 			    //边结构体
    int Find(int *parent,int x){
         while(parent[x]>=0) x=parent[x];  //循环向上寻找下标为x顶点的根
         return  x;  					   //while循环结束时找到了根的下标
    }
    Edge edges[MaxEdge];   				   //边数组
    int parent[MaxVex];         		   //父亲顶点数组(并查集)
    Void MiniSpanTree_Kruskal(MGraph G){
           int  i , n , m;
           sort(edges); 				   //按权值由小到大对边排列（省略了细节）
           for(i=0 ; i<G.vexnum ; i++)parent[i]=-1;  //初始化：各个顶点单独形成一个集合
           for(i=0 ; i<G.arcnum ; i++){    //扫描每条边
                     n=Find(parent,edges[i].a);    //n是这条边第一个顶点的根顶点所在下标
                     m=Find(parent,edges[i].b);    //m是这条边第二个顶点的根顶点所在下标
                      if(n!=m){                    //根顶点不相同 这条边不会构成环
                                  parent[n]=m;     //并操作
                                  //作为生成树的一条边打印出来
                                  printf(“(%d->%d) ”,edges[i].a,edges[i].b); 
                      }
           }
    }

看一个例子，[视频讲解][Link 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]

克鲁斯卡尔算法操作分为对边的权值排序部分和一个单重for循环，它们是并列关系，由于排序耗费时间大于单重循环，所以克鲁斯卡尔算法的主要时间耗费在排序上。排序和图中边的数量有关系，所以适合稀疏图。

## 最短路径 ##

### 问题分类 ###

单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径  
多源最短路径问题：求任意两顶点间的最短路径  
![在这里插入图片描述][20190825180600637.png]

### 迪杰斯特拉算法 ###

该算法设置一个集合S记录已求得的最短路径的顶点，可用一个数组s\[\]来实现，初始化为0，当s\[vi\]=1时表示将顶点vi放入S中，初始时把源点v0放入S中。此外，在构造过程中还设置了两个辅助数组：  
dist\[\]：记录了从源点v0到其他各顶点当前的最短路径长度，dist\[i\]初值为arcs\[v0\]\[i\]。  
path\[\]：path\[i\]表示从源点到顶点i之间的最短路径的前驱结点，在算法结束时，可根据其值追溯得到源点v0到顶点vi的最短路径。

假设从顶点0出发，也就是顶点0为源点，集合S最初只包含顶点0，邻接矩阵arcs表示带权有向图，arcs\[i\]\[j\]表示有向边<i，j>的权值，若不存在有向边<i，j>，则arcs\[i\]\[j\]为∞。Dijkstra算法的步骤如下：  
1）初始化：集合S初始为\{0\}，dist\[\]的初始值dist\[i\]=arcs\[0\]\[i\]，i=1，2，…，n-1。  
2）找出dist\[\]中的最小值dist\[j\]，将顶点j加入集合S，即修改s\[vj\]=1。  
3）修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：如果dist\[j\] + arcs\[j\]\[k\]< dist\[k\]，则令dist\[k\]=dist\[j\] + arcs\[j\]\[k\]。另外更新path\[k\]=j(也就是顶点j加入集合之后如果有新的路径使得到顶点k路径变短的话就将到顶点k的路径长度修改成较短的)  
4）重复2）～3）操作共n-1次，直到所有的顶点都包含在S中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 4]  
具体过程可参考 [视频讲解][Link 4]

Void Dijkstra(MGraph G,int v,int path[ ],int dist[ ]){ //v是源点的下标 
    	int s[maxSize]; //数组s记录当前找到了到哪些顶点的最短路径 找到了对应值为1 没找的对应值为0
    	int i,j,min,u; 
    	//初始化 将path dist s 数组的初值确定
    	for(i=0 ; i<G.vexnum ; i++){
    		dist[i]=G.edge[v][i]; //dist初值为源点到各个顶点的边的权值
    		s[i]=0; //一开始没有一个顶点
    		if(G.edge[v][i]<65535)path[i]=v;  //与源点连通的顶点的path值存源点下标
    		else path[i]=-1;//刚开始到源点没有路径的顶点path值为-1
    	}
    	s[v]=1; //源点加入集合s
    	path[v]=-1; //源点不存在到自身的路径
    	//下面的循环中包含两部分作用：
    	//①内层第一个for循环是找到 到剩余顶点中距离最小的 顶点u 并把它加入最短路径
        //②内层第二个for循环是由新加入的顶点u来判断是否找到了新的更短路径，如果有就更新，没有就不做任何操作
                                                                    
    	for(i=0;i<G.vexnum;i++){
    		min=65535;
    		for(j=0;j<G.vexnum;j++){
    			if(s[j]==0&&dist[j]<min){ //从剩余的顶点中找到距离最小的顶点
    				u=j;    //u用于保存当前找到的距离最小的顶点下标 当循环结束u保存的就是最小距离的顶点下标
    				min=dist[j]; 
    			}
    		}
    		s[u]=1;//到u的距离是最小的，所以把顶点u加入最短路径
    		for(i=0;i<G.vexnum;i++){
    			min=65535;
    			for(j=0;j<G.vexnum;j++){
    				if(s[j]==0&&dist[j]<min){ //从剩余的顶点中找到距离最小的顶点
    					u=j;    //u用于保存当前找到的距离最小的顶点下标 当循环结束u保存的就是最小距离的顶点下标
    					min=dist[j]; 
    				}
    			}	
    			s[u]=1;//到u的距离是最小的，所以把顶点u加入最短路径
    
    			for(j=0;j<G.vexnum;j++){
    				if(s[j]==0 && dist[u]+G.Edges[u][j]<dist[j]){
    					dist[j]=dist[u]+G.Edges[u][i];//如果由新加入最短路径的顶点u到其他剩余顶点的距离变短了则
                                                                         //修改到剩余顶点的距离为较小值  
    					path[j]=u;//这条较短的路径是由顶点u过来的  
    				} 
    			}
    		}
    	}
    }

##### 时间复杂度 #####

迪杰斯特拉算法的核心部分在于一个双重循环，这个双重循环的内循环又是两个并列的单重for循环组成(找距离最小顶点和更新距离),任意取其中一个循环中的操作为基本操作，都可以得出迪杰斯特拉算法的时间复杂度为O(n2) 其中n为图中的顶点数。  
迪杰斯特拉算法不能用于权值有负数的图，不然结果会出错！

### 弗洛伊德算法 ###

#### 算法思想 ####

递推产生一个n阶方阵序列A(−1)，A(0)，…，A(k)，…，A(n−1)  
其中A(k)\[i\]\[j\]表示从顶点vi到顶点vj的路径长度，k表示绕行第k个顶点的运算步骤。初始时，对于任意两个顶点vi和vj，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以∞作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点k(k=0，1，…，n-1)作为中间顶点。如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径。

void Floyd(MGraph G,int Path[][]){
    	int i, j, k ;
    	int A[MaxSize][MaxSize];
    	//对数组A[][]和Path[][]进行初始化
    	for(i=0; i<G.vexnums; i++){
    		for(j=0; j<G.vexnums; j++){
    			A[i][j]=G.Edges[i][j];
    			Path[i][j]=-1;
    		}
    	}
    	for(k=0; k<G.vexnums; k++){
    		for(i=0; i<G.vexnums; i++){
    			for(j=0; j<G.vexnums; j++){
    				if(A[i][j]>A[i][k]+A[k][j]){//如果顶点i到顶点j的距离比顶点i经过顶点k到顶点j的距离长，则更新从顶点i到顶点j的距离为较小值，并且存储k表示路径经过顶点k
    					A[i][j]=A[i][k]+A[k][j];
    					Path[i][j]=k;
    				}
    			}
    		}
    	}
    }

弗洛伊德算法的核心为一个三重循环，所以时间复杂度为O(n3) 其中n是图中的顶点数。

### 拓扑排序 ###

#### AOV ####

如果我们把每个环节看成图中一个顶点，在这样一个有向图中，用顶点表示活动，用弧表示活动之间的优先关系，那么这样的有向图称为AOV网(Activity On Vertex)  
由于弧是用来表示活动之间的优先关系，或者说AOV网具有实际的意义，那么AOV网显然是不能有回路的  
有向无环图也叫做DAG图

拓扑序列是对图中所有的顶点，如果存在一条从顶点A到顶点B的路径，那么在排序中顶点A出现在顶点B的前面。

拓扑排序就是对一个有向图构造拓扑序列的过程，构造会有两种结果：

1.  如果此图全部顶点都被输出了，说明它是不存在回路的AOV网；
2.  如果没有输出全部顶点，则说明这个图存在回路，不是AOV网。

#### 拓扑排序算法 ####

从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为弧尾的弧。重复这个步骤直到输出图中全部顶点，或者找不到入度为0的顶点为止。  
一个DAG的拓扑排序不唯一  
由于拓扑排序需要删除边和顶点，所以使用邻接表存储图比较方便。

bool TopologicalSort(Graph G){
    	InitStack(S);			//初始化栈，存储入度为0的顶点
    	for(int i=0;i<G.vexnum;i++)
    		if(indegree[i]==0)Push(S,i);	//将所有入度为0的顶点进栈
    	int count=0;			//计数，记录当前已经输出的顶点数
    	while(!IsEmpty(S)){			//栈不空，则存在入度为0的顶点
    		Pop(S,i);			//栈顶元素出栈
                                     pritnf(“%d”,G.adjlist[i]);
    		for(ArcNode *p=G.vertices[i].firstarc; p; p=p->nextarc){
    			v=p->adjvex;                         //取这条弧指向的顶点
    			if(!(--indegree[v]))Push(S,v);   //入度减1为0，则入栈
    		}
    	}
    	if(count<G.vexnum)return  false;    //排序失败，有向图中有回路
    	else return  true; 	//拓扑排序成功
    }

拓扑排序对AOV图需要打印图中所有顶点，而且由于要删除边(实际没有删除，只是寻找入度为0的顶点)所以对所有边也要进行扫描，所以这个算法的时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O (|V|+|E|) O(∣V∣\+∣E∣)

1.  拓扑排序从入度为0的顶点开始筛选，对应的实际意义是工程可以从这个活动开始或者继续。
2.  拓扑序列可以不唯一，当活动排成线性，则拓扑序列是唯一的。
3.  对于一般的图，如果它的邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立  
    只要按照序号从小到大或者从大到小的顺序就能得到这个邻接矩阵为三角矩阵的图的拓扑序列。

上三角：0 1 2 3 下三角：3 2 1 0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 5]

### 关键路径 ###

AOE(Activity On Edge):在一个表示工程的带权有向图中，**用顶点表示事件，用有向边表示活动**，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网称为AOE网。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 6]  
活动是在边上，边上的权值表示的是这个活动所需要耗费的时间。AOE网是在AOE的基础上来分析工程的最少需要时间。或者是为了缩短工期，需要找出哪些活动是要加快的。  
开始时间为0 设定造好各个模块的时间为5 因为最长路径为5  
造轮子最早发生的时间：0 最晚发生的时间：3  
造零件最早发生的时间：0 最晚发生的时间：4  
造发动机最早发生的时间：0 最晚发生的时间：0  
**关键活动的最早发生时间和最晚发生时间是一样的！**

例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 10]

#### 参考资料 ####

王道数据结构

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/1de22940078c4727af9d257ca4afd800.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/2972701f489e430da7790f0fd8088c8d.png
[20190826103821658.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/9c629bd4128d444ba119f871b34f9360.png
[Link 1]: https://www.bilibili.com/video/av39171741?t=74&p=26
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/7035b765157248b583a11ae2b7157225.png
[Link 2]: https://blog.csdn.net/weixin_37551036/article/details/99898568
[Link 3]: https://blog.csdn.net/weixin_37551036/article/details/100054561
[Link 4]: https://www.bilibili.com/video/av39171741/?p=25
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/5185e46104f543e7a3fca4c584a7c01b.png
[20190825180600637.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/ed0db1c94ac940dfa31c66efc6ee1ccc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/f0eed46ebb7d4c2db540916c9b97b544.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/a931d36de2274a0ba88f2fa551661b8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/fe7a9dfe4525497a8df772e6efb2b810.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/7e8e930fad5a47e1a6d044f2cf9c6a6f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/83b5bcdc2e5b485aa8c1ccbb20f510fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/5ce57891ce5848ffbfecb2f47f7ef9bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 10]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/16/5bdc46345a554699b16ba104cd5e12a0.png