图的应用

朱雀 2022-03-26 14:56 181阅读 0赞

# 1. 图的应用总览 #

在数据结构中图的应用很广泛，本文主要从以下四个方面介绍：  
①最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权数之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。  
②拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。  
③关键路径：在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度，路径长度最长的路径叫做关键路径(Critical Path)。  
④最短路径：最短路径问题是图研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

#    2. 最小生成树 #

问题提出：  
要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。  
问题分析：  
答案只能从生成树中找，因为要做到任何两个城市之间有线路可达，通信网必须是连通的；但对长度最小的要求可以知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。  
结论：  
希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 —— 最小代价生成树。  
构造最小生成树的算法很多，其中多数算法都利用了一种称之为 MST 的性质。  
MST 性质：设 N = (V, E) 是一个连通网，U是顶点集 V的一个非空子集。若边 (u, v) 是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u, v) 的最小生成树。

#    （1）普里姆 (Prim) 算法 #

算法思想：  
①设 N=(V, E)是连通网，TE是N上最小生成树中边的集合。  
②初始令 U=\{u\_0\}, (u\_0∈V), TE=\{ \}。  
③在所有u∈U，u∈U-V的边(u,v)∈E中，找一条代价最小的边(u\_0,v\_0 )。  
④将(u\_0,v\_0 )并入集合TE，同时v\_0并入U。  
⑤重复上述操作直至U = V为止，则 T=(V,TE)为N的最小生成树。

![At7hk7YejJNJ2aiV45Zmng.png][]  
代码实现：

void MiniSpanTree_PRIM(MGraph G,VertexType u)
    	//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
    	//记录从顶点集U到V-U的代价最小的边的辅助数组定义；
    	//closedge[j].lowcost表示在集合U中顶点与第j个顶点对应最小权值
    {
    	int k, j, i;
    	k = LocateVex(G,u);
    	for (j = 0; j < G.vexnum; ++j)	//辅助数组的初始化
    		if(j != k)
    		{
    			closedge[j].adjvex = u;
    			closedge[j].lowcost = G.arcs[k][j].adj;	
    //获取邻接矩阵第k行所有元素赋给closedge[j!= k].lowcost
    		}
    	closedge[k].lowcost = 0;		
    //初始，U = {u};  
    	PrintClosedge(closedge,G.vexnum);
    	for (i = 1; i < G.vexnum; ++i)	\
    //选择其余G.vexnum-1个顶点，因此i从1开始循环
    	{
    		k = minimum(G.vexnum,closedge);		
    //求出最小生成树的下一个结点：第k顶点
    		PrintMiniTree_PRIM(G, closedge, k); 	//输出生成树的边
    		closedge[k].lowcost = 0;				//第k顶点并入U集
    		PrintClosedge(closedge,G.vexnum);
    		for(j = 0;j < G.vexnum; ++j)
    		{                                           
    			if(G.arcs[k][j].adj < closedge[j].lowcost)	
    //比较第k个顶点和第j个顶点权值是否小于closedge[j].lowcost
    			{
    				closedge[j].adjvex = G.vexs[k];//替换closedge[j]
    				closedge[j].lowcost = G.arcs[k][j].adj;
    				PrintClosedge(closedge,G.vexnum);
    			}
    		}
    	}
    }

## （2）克鲁斯卡尔 (Kruskal) 算法 ##

算法思想：  
①设连通网 N = (V, E )，令最小生成树初始状态为只有n个顶点而无边的非连通图，T=(V, \{ \})，每个顶点自成一个连通分量。  
②在 E 中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。  
③依此类推，直至 T 中所有顶点都在同一连通分量上为止。  
![vvpnNuZ294scW8rRyxJz52.png][]![CSC9hYkE3tUYEfuWvVY2MV.png][]  
最小生成树可能不惟一！

#    3. 拓扑排序 #

##    （1）有向无环图 ##

无环的有向图，简称 DAG (Directed Acycline Graph) 图。  
![HhfPzp9xiWbcNriWLdeZxn.png][]  
有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几乎所有的工程都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定条件的约束，例如：其中某些子工程必须在另一些子工程完成之后才能开始。  
对整个工程和系统，人们关心的是两方面的问题：  
①工程能否顺利进行；  
②完成整个工程所必须的最短时间。  
对应到有向图即为进行拓扑排序和求关键路径。  
AOV网：  
用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网(Activity On Vertex network)。  
例如：排课表  
![6SvwTSFLfQWoUacXMyQNYn.png][]![KNNtefSpziGbPBoKrEt2Li.png][]  
AOV网的特点：  
①若从i到j有一条有向路径，则i是j的前驱；j是i的后继。  
②若< i , j >是网中有向边，则i是j的直接前驱；j是i的直接后继。  
③AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

问题：  
问题：如何判别 AOV 网中是否存在回路？  
检测 AOV 网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

拓扑排序的方法：  
①在有向图中选一个没有前驱的顶点且输出之。  
②从图中删除该顶点和所有以它为尾的弧。  
③重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。  
![3LZ4vgTkHBFyWNA4axAq5f.png][]![hKmgWfeeasrb23epjExVpP.png][]  
一个AOV网的拓扑序列不是唯一的！  
代码实现：

Status TopologicalSort(ALGraph G)
    	//有向图G采用邻接表存储结构。
    	//若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR.
    	//输出次序按照栈的后进先出原则，删除顶点，输出遍历
    {
    	SqStack S;
    	int i, count;
    	int *indegree1 = (int *)malloc(sizeof(int) * G.vexnum);
    	int indegree[12] = {0};
    	FindInDegree(G, indegree);	//求个顶点的入度下标从0开始
    	InitStack(&S);
    	PrintStack(S);
    	for(i = 0; i < G.vexnum; ++i)
    		if(!indegree[i])		//建0入度顶点栈S
    			push(&S,i);		//入度为0者进栈
    	count = 0;				//对输出顶点计数
    	while (S.base != S.top)
    	{
    		ArcNode* p;
    		pop(&S,&i);
    		VisitFunc(G,i);//第i个输出栈顶元素对应的顶点，也就是最后进来的顶点	
    		++count;		  //输出i号顶点并计数
    		for(p = G.vertices[i].firstarc; p; p = p->nextarc)
    		{	//通过循环遍历第i个顶点的表结点，将表结点中入度都减1
    			int k = p->adjvex;	//对i号顶点的每个邻接点的入度减1
    			if(!(--indegree[k]))
    				push(&S,k);		//若入度减为0，则入栈
    		}//for
    	}//while
    	if(count < G.vexnum)
    	{
    		printf("\n该有向图有回路!\n");
    		return ERROR;	//该有向图有回路
    	}
    	else
    	{
    		printf("\n该有向图没有回路!\n");
    		return OK;
    	}
    }

## 关键路径 ##

把工程计划表示为有向图，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。称这种有向图为边表示活动的网，简称为 AOE网 (Activity On Edge)。  
例如：  
设一个工程有11项活动，9个事件。  
事件v\_1——表示整个工程开始（源点）  
事件v\_9——表示整个工程结束（汇点）

![GyYULtXvC68x6VV5wmhmrX.png][]  
对AOE网，我们关心两个问题：  
①完成整项工程至少需要多少时间？  
②哪些活动是影响工程进度的关键？  
关键路径——路径长度最长的路径。  
路径长度——路径上各活动持续时间之和。  
v\_i——表示事件v\_i的最早发生时间。假设开始点是v\_1，从v\_1到〖v﷩i〗的最长路径长度。ⅇ(ⅈ)——表示活动a\_i的最早发生时间。  
l(ⅈ)——表示活动a\_i最迟发生时间。在不推迟整个工程完成的前提下，活动a\_i最迟必须开始进行的时间。  
l(ⅈ)-ⅇ(ⅈ)意味着完成活动a\_i的时间余量。  
我们把l(ⅈ)=ⅇ(ⅈ)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程进度。  
例如上图中网，从从v\_1到v\_9的最长路径是(v\_1,v\_2,v\_5,v\_8,ν\_9 )，路径长度是18，即ν\_9的最迟发生时间是18。而活动a\_6的最早开始时间是5，最迟开始时间是8，这意味着：如果a\_6推迟3天或者延迟3天完成，都不会影响整个工程的完成。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。  
由上面介绍可知：辨别关键活动是要找l(ⅈ)=ⅇ(ⅈ)的活动。为了求ⅇ(ⅈ)和l(ⅈ)，首先应求得事件的最早发生时间vⅇ(j)和最迟发生时间vl(j)。如果活动a\_i由弧〈j,k〉表示，其持续时间记为dut(〈j,k〉),则有如下关系：  
ⅇ(ⅈ)= vⅇ(j)  
l(ⅈ)=vl(k)-dut(〈j,k〉)  
求vⅇ(j)和vl(j)需分两步进行：  
第一步：从vⅇ(0)=0开始向前递推  
vⅇ(j)=Max\{vⅇ(i)+dut(〈j,k〉)\} 〈i,j〉∈T,j=1,2,…,n-1  
其中，T是所有以第j个顶点为头的弧的集合。  
第二步：从vl(n-1)=vⅇ(n-1)起向后递推  
vl(i)=Min\{vl(j)-dut(〈i,j〉)\} 〈i,j〉∈S,i=n-2,…,0  
其中，S是所有以第i个顶点为尾的弧的集合。  
下面我们以上图AOE网为例，先求每个事件v\_i的最早发生时间，再逆向求每个事件对应的最晚发生时间。再求每个活动的最早发生时间和最晚发生时间，如下面表格：  
![tPQo3f6GM5YUJ7YtvKQEDF.png][]![JdZnbRYWEhrHvasX7qVb6h.png][]  
在活动的统计表中，活动的最早发生时间和最晚发生时间相等的，就是关键活动

##    关键路径的讨论： ##

①若网中有几条关键路径，则需加快同时在几条关键路径上的关键活动。 如：a11、a10、a8、a7。  
②如果一个活动处于所有的关键路径上，则提高这个活动的速度，就能缩短整个工程的完成时间。如：a1、a4。  
③处于所有关键路径上的活动完成时间不能缩短太多，否则会使原关键路径变成非关键路径。这时必须重新寻找关键路径。如：a1由6天变成3天，就会改变关键路径。

关键路径算法实现：

int CriticalPath(ALGraph G)
    {	//因为G是有向网，输出G的各项关键活动
    	SqStack T;
    	int i, j;	ArcNode* p;
    	int k , dut;
    	if(!TopologicalOrder(G,T))
    		return 0;
    	int vl[VexNum];
    	for (i = 0; i < VexNum; i++)
    		vl[i] = ve[VexNum - 1];		//初始化顶点事件的最迟发生时间
    	while (T.base != T.top)			//按拓扑逆序求各顶点的vl值
    	{
    
    		for(pop(&T, &j), p = G.vertices[j].firstarc; p; p = p->nextarc)
    		{
    			k = p->adjvex;	dut = *(p->info);	//dut<j, k>
    			if(vl[k] - dut < vl[j])
    				vl[j] = vl[k] - dut;
    		}//for
    	}//while
    	for(j = 0; j < G.vexnum; ++j)	//求ee,el和关键活动
    	{
    		for (p = G.vertices[j].firstarc; p; p = p->nextarc)
    		{
    			int ee, el;		char tag;
    			k = p->adjvex;	dut = *(p->info);
    			ee = ve[j];	el = vl[k] - dut;
    			tag = (ee == el) ? '*' : ' ';
    			PrintCriticalActivity(G,j,k,dut,ee,el,tag);
    		}
    	}
    	return 1;
    }

# 4.最短路 #

典型用途：交通网络的问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？  
![nxzxVKbc7ojqEvBxP4cs3B.png][]  
交通网络用有向网来表示：顶点——表示城市，弧——表示两个城市有路连通，弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。  
如何能够使一个城市到另一个城市的运输时间最短或运费最省？这就是一个求两座城市间的最短路径问题。  
问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n - 1条边。  
常见最短路径问题：单源点最短路径、所有顶点间的最短路径  
（1）如何求得单源点最短路径？  
穷举法：将源点到终点的所有路径都列出来，然后在其中选最短的一条。但是，当路径特别多时，特别麻烦；没有规律可循。  
迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生各顶点的最短路径。  
路径长度最短的最短路径的特点：  
在此路径上，必定只含一条弧 <v\_0, v\_1>，且其权值最小。由此，只要在所有从源点出发的弧中查找权值最小者。  
下一条路径长度次短的最短路径的特点：  
①、直接从源点到v\_2<v\_0, v\_2>（只含一条弧）；  
②、从源点经过顶点v\_1，再到达v\_2<v\_0, v\_1>,<v\_1, v\_2>（由两条弧组成）  
再下一条路径长度次短的最短路径的特点：  
有以下四种情况：  
①、直接从源点到v\_3<v\_0, v\_3>（由一条弧组成）；  
②、从源点经过顶点v\_1，再到达v\_3<v\_0, v\_1>,<v\_1, v\_3>（由两条弧组成）；  
③、从源点经过顶点v\_2，再到达v\_3<v\_0, v\_2>,<v\_2, v\_3>（由两条弧组成）；  
④、从源点经过顶点v\_1 ,v\_2，再到达v\_3<v\_0, v\_1>,<v\_1, v\_2>,<v\_2, v\_3>（由三条弧组成）；  
其余最短路径的特点:  
①、直接从源点到v\_i<v\_0, v\_i>（只含一条弧）；  
②、从源点经过已求得的最短路径上的顶点，再到达v\_i（含有多条弧）。  
Dijkstra算法步骤：  
初始时令S=\{v\_0\}, T=\{其余顶点\}。T中顶点对应的距离值用辅助数组D存放。  
D\[i\]初值：若<v\_0, v\_i>存在，则为其权值；否则为∞。  
从T中选取一个其距离值最小的顶点v\_j，加入S。对T中顶点的距离值进行修改：若加进v\_j作中间顶点，从v\_0到v\_i的距离值比不加 vj 的路径要短，则修改此距离值。  
重复上述步骤，直到 S = V 为止。

算法实现：

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
    { // 用Dijkstra算法求有向网 G 的 v0 顶点到其余顶点v的最短路径P[v]及带权长度D[v]。
    	// 若P[v][w]为TRUE,则 w 是从 v0 到 v 当前求得最短路径上的顶点。  P是存放最短路径的矩阵，经过顶点变成TRUE
    	// final[v]为TRUE当且仅当 v∈S,即已经求得从v0到v的最短路径。
    	int v,w,i,j,min;
    	Status final[MAX_VERTEX_NUM];
    	for(v = 0 ;v < G.vexnum ;++v)
    	{
    		final[v] = FALSE;
    		D[v] = G.arcs[v0][v].adj;		//将顶点数组中下标对应是 v0 和 v的距离给了D[v]
    		for(w = 0;w < G.vexnum; ++w)
    			P[v][w] = FALSE;			//设空路径
    		if(D[v] < INFINITY)
    		{
    			P[v][v0] = TRUE;
    			P[v][v] = TRUE;
    		}
    	}
    	D[v0]=0;
    	final[v0]= TRUE; /* 初始化,v0顶点属于S集 */
    	for(i = 1;i < G.vexnum; ++i) /* 其余G.vexnum-1个顶点 */
    	{ /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
    		min = INFINITY; /* 当前所知离v0顶点的最近距离 */
    		for(w = 0;w < G.vexnum; ++w)
    			if(!final[w]) /* w顶点在V-S中 */
    				if(D[w] < min)
    				{
    					v = w;
    					min = D[w];
    				} /* w顶点离v0顶点更近 */
    				final[v] = TRUE; /* 离v0顶点最近的v加入S集 */
    				for(w = 0;w < G.vexnum; ++w) /* 更新当前最短路径及距离 */
    				{
    					if(!final[w] && min < INFINITY && G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w]))
    					{ /* 修改D[w]和P[w],w∈V-S */
    						D[w] = min + G.arcs[v][w].adj;
    						for(j = 0;j < G.vexnum;++j)
    							P[w][j] = P[v][j];
    						P[w][w] = TRUE;
    					}
    				}
    	}
    }

[At7hk7YejJNJ2aiV45Zmng.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/At7hk7YejJNJ2aiV45Zmng.png
[vvpnNuZ294scW8rRyxJz52.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/vvpnNuZ294scW8rRyxJz52.png
[CSC9hYkE3tUYEfuWvVY2MV.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/CSC9hYkE3tUYEfuWvVY2MV.png
[HhfPzp9xiWbcNriWLdeZxn.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/HhfPzp9xiWbcNriWLdeZxn.png
[6SvwTSFLfQWoUacXMyQNYn.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/6SvwTSFLfQWoUacXMyQNYn.png
[KNNtefSpziGbPBoKrEt2Li.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/KNNtefSpziGbPBoKrEt2Li.png
[3LZ4vgTkHBFyWNA4axAq5f.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/3LZ4vgTkHBFyWNA4axAq5f.png
[hKmgWfeeasrb23epjExVpP.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/hKmgWfeeasrb23epjExVpP.png
[GyYULtXvC68x6VV5wmhmrX.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/GyYULtXvC68x6VV5wmhmrX.png
[tPQo3f6GM5YUJ7YtvKQEDF.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/tPQo3f6GM5YUJ7YtvKQEDF.png
[JdZnbRYWEhrHvasX7qVb6h.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/JdZnbRYWEhrHvasX7qVb6h.png
[nxzxVKbc7ojqEvBxP4cs3B.png]: http://usercontent.edu2act.cn/media/ckeditor/upload2018/1203/nxzxVKbc7ojqEvBxP4cs3B.png