数据结构——图的应用

杨伟彬
杨伟彬   发布于 2018-12-07 13:55
阅读量: 223

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的最小生成树。

 
代码实现:

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 中所有顶点都在同一连通分量上为止。
      
    最小生成树可能不惟一!
3. 拓扑排序
(1)有向无环图
    无环的有向图,简称 DAG (Directed Acycline Graph) 图。
 
有向无环图在工程计划和管理方面的应用:除最简单的情况之外,几乎所有的工程都可分为若干个称作“活动”的子工程,并且这些子工程之间通常受着一定条件的约束,例如:其中某些子工程必须在另一些子工程完成之后才能开始。
对整个工程和系统,人们关心的是两方面的问题: 
①工程能否顺利进行; 
②完成整个工程所必须的最短时间。
对应到有向图即为进行拓扑排序和求关键路径。 
AOV网: 
    用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网(Activity On Vertex network)。
例如:排课表
      
AOV网的特点:
①若从i到j有一条有向路径,则i是j的前驱;j是i的后继。
②若< i , j >是网中有向边,则i是j的直接前驱;j是i的直接后继。
③AOV网中不允许有回路,因为如果有回路存在,则表明某项活动以自己为先决条件,显然这是荒谬的。
问题:    
    问题:如何判别 AOV 网中是否存在回路?
    检测 AOV 网中是否存在环方法:对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网必定不存在环。
拓扑排序的方法:
    ①在有向图中选一个没有前驱的顶点且输出之。
    ②从图中删除该顶点和所有以它为尾的弧。
    ③重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止。
        
    一个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;
	}
}

(3)关键路径
    把工程计划表示为有向图,用顶点表示事件,弧表示活动,弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。称这种有向图为边表示活动的网,简称为 AOE网 (Activity On Edge)。
例如:
设一个工程有11项活动,9个事件。
事件v_1——表示整个工程开始(源点) 
事件v_9——表示整个工程结束(汇点)

 
对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的最早发生时间,再逆向求每个事件对应的最晚发生时间。再求每个活动的最早发生时间和最晚发生时间,如下面表格:
          
在活动的统计表中,活动的最早发生时间和最晚发生时间相等的,就是关键活动。
(3)关键路径的讨论:
①若网中有几条关键路径,则需加快同时在几条关键路径上的关键活动。      如: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.最短路径
    典型用途:交通网络的问题——从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短?
 
    交通网络用有向网来表示:顶点——表示城市,弧——表示两个城市有路连通,弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。
    如何能够使一个城市到另一个城市的运输时间最短或运费最省?这就是一个求两座城市间的最短路径问题。
    问题抽象:在有向网中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;
					}
				}
	}
}


       
    

收藏 转发 评论 1

这写的忒好了