数据结构(六)——图的应用

6.4 图的应用

6.4.1 最小生成树

对于⼀个带权连通⽆向图G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有⽣成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree, MST）。

最小生成树可能有多个，但边的权值之和总是唯一且最小的
最小生成树的边数=顶点数–1。砍掉一条则不连通，增加一条边则会出现回路

求最小生成树
Prim算法(普里姆):
从某一个顶点开始构建生成树;
每次将代价最小的新顶点纳入生成树，
直到所有顶点都纳入为止。

Kruskal算法(克鲁斯卡尔):
每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选)
直到所有结点都连通

Prim算法的实现思想
第1轮:循环遍历所有个结点，找到lowCost最低的，且还没加入树的顶点
第2轮︰循环遍历所有个结点，找到lowCost最低的，且还没加入树的顶点
第3轮:循环遍历所有个结点，找到lowCost最低的，且还没加入树的顶点
第4轮:循环遍历所有个结点，找到lowCost最低的，且还没加入树的顶点
第5轮：循环遍历所有个结点，找到lowCost最低的，且还没加入树的顶点

Kruskal 算法的实现思想
第1轮：检查第1条边的两个顶点是否连通（是否属于同⼀个集合）
第2轮：检查第2条边的两个顶点是否连通（是否属于同⼀个集合）
第3轮：检查第3条边的两个顶点是否连通（是否属于同⼀个集合）
第4轮：检查第4条边的两个顶点是否连通（是否属于同⼀个集合）
第5轮：检查第5条边的两个顶点是否连通（是否属于同⼀个集合）
第6轮：检查第6条边的两个顶点是否连通（是否属于同⼀个集合）

6.4.2_1 最短路径问题_BFS算法

BFS求无权图的单源最短路径

#define MAX_LENGTH 2147483647			//地图中最大距离，表示正无穷//求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){//d[i]表示从u到i结点的最短路径for(i=0; i<G.vexnum; i++){visited[i]=FALSE;				//初始化访问标记数组d[i]=MAX_LENGTH;				//初始化路径长度path[i]=-1;						//初始化最短路径记录}InitQueue(Q);						//初始化辅助队列d[u]=0;visites[u]=TREE;EnQueue(Q,u);while(!isEmpty[Q]){					//BFS算法主过程DeQueue(Q,u);					//队头元素出队并赋给ufor(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){if(!visited[w]){            //w为u的尚未访问的邻接顶点d[w]=d[u]+1;            //路径长度＋1path[w]=u;              //最短路径应从u到wvisited[w]=TREE;        //设已访问标记EnQueue(Q,w);			//顶点w入队}}}
}

6.4.2_2 最短路径问题_Dijkstra算法

使用 Dijkstra算法求最短路径问题，需要使用三个数组：
final[]数组用于标记各顶点是否已找到最短路径。
dist[]数组用于记录各顶点到源顶点的最短路径长度。
path[]数组用于记录各顶点现在最短路径上的前驱。

算法思想：循环遍历所有结点，找到还没确定最短路径、且dist最小的顶点Vi，令final[i]=ture。
检查所有邻接自Vi的顶点，若其final值为false,则更新dist和path信息。

#define MAX_LENGTH = 2147483647;// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){for(int i=0; i<G.vexnum; i++){		//初始化数组final[i]=FALSE;dist[i]=G.edge[u][i];if(G.edge[u][i]==MAX_LENGTH || G.edge[u][i] == 0)path[i]=-1;elsepath[i]=u;final[u]=TREE;}for(int i=0; i<G.vexnum; i++){int MIN=MAX_LENGTH;int v;// 循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点vfor(int j=0; j<G.vexnum; j++){if(final[j]!=TREE && dist[j]<MIN){MIN = dist[j];v = j;}}final[v]=TREE;// 检查所有邻接⾃v的顶点路径长度是否最短for(int j=0; j<G.vexnum; j++){if(final[j]!=TREE && dist[j]>dist[v]+G.edge[v][j]){dist[j] = dist[v]+G.edge[v][j];path[j] = v;}}}
}

Dijkstra算法能够很好的处理带权图的单源最短路径问题，但不适⽤于有负权值的带权图。

6.4.2_3 最短路径问题_Floyd算法

Floyd算法：求出每⼀对顶点之间的最短路径，使⽤动态规划思想，将问题的求解分为多个阶段。

Floyd算法使用到两个矩阵：
dist[]：目前各顶点间的最短路径。
path[]：两个顶点之间的中转点。

//...准备工作，根据图的信息初始化矩阵A和pathfor(k=0;k<n;k++){                //考虑以Vk作为中转点for(i=0;i<n;i++){            //遍历整个矩阵，i为行号，j为列号for(j=0;j<n;j++){if(A[i][j]>A[i][k]+A[k][j]){    //以Vk为中转地按的路径更短A[i][j]=A[i][k]+A[k][j];    //更新最短路径长度path[i][j]=k;               //中转点}}}}

Floyd算法不能解决带有“负权回路”的图(有负权值的边组成回路)，这种图有可能没有最短路径

最短路径算法比较：

	BFS算法	Dĳkstra算法	Floyd算法
无权图	✔	✔	✔
带权图	✘	✔	✔
带负权值的图	✘	✘	✔
带负权回路的图	✘	✘	✘
时间复杂度	O(\|V\|^2)或O(\|V\|+\|E\|)	O(\|V\|^2)	O(\|V\|^3)
通常用于	求无权图的单源最短路径	求带权图的单源最短路径	求带权图中各顶点间的最短路径

6.4.3 有向无环图描述表达式

有向无环图:若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)

解题方法

练习

6.4.4 拓扑排序

AOV网(Activity on vertex Network，用顶点表示活动的网):
用DAG图(有向无环图）表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行

拓扑排序︰在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序:
①每个顶点出现且只出现一次。
②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为:拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

拓扑排序的实现：
① 从AOV网中选择⼀个没有前驱（入度为0）的顶点并输出。
② 从网中删除该顶点和所有以它为起点的有向边。
③ 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止

代码实现拓扑排序

#define MaxVertexNum 100			//图中顶点数目最大值typedef struct ArcNode{				//边表结点int adjvex;						//该弧所指向的顶点位置struct ArcNode *nextarc;		//指向下一条弧的指针
}ArcNode;typedef struct VNode{				//顶点表结点VertexType data;				//顶点信息ArcNode *firstarc;				//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];typedef struct{AdjList vertices;				//邻接表int vexnum,arcnum;				//图的顶点数和弧数
}Graph;								//Graph是以邻接表存储的图类型// 对图G进行拓扑排序
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)){				//栈不空，则存入Pop(S,i);					//栈顶元素出栈print[count++]=i;			//输出顶点ifor(p=G.vertices[i].firstarc;p;p=p=->nextarc){//将所有i指向的顶点的入度减1，并将入度为0的顶点压入栈v=p->adjvex;if(!(--indegree[v]))Push(S,v);			//入度为0，则入栈}}if(count<G.vexnum)return false;				//排序失败,有向图中有回路elsereturn true;				//拓扑排序成功
}

拓扑排序每个顶点都需要处理一次每条边都需要处理一次
时间复杂度：O(|V|+|E|)
若采用邻接矩阵，则需O(|V^2|)

逆拓扑排序
对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序:
①从AOV网中选择一个没有后继（出度为O)的顶点并输出。
②从网中删除该顶点和所有以它为终点的有向边。
③重复①和②直到当前的AOV网为空。

逆拓扑排序的实现(DFS算法)

void DFSTraverse(Graph G){    //对图G进行深度优先遍历for(v=0; v<G.vexnum;++V)visited[v]=FALSE;     //初始化已访问标记数据for(v=;v<G.vexnum; ++V)   //本代码中是从v=0开始遍历if(!visited[v])DFS(G,v);
}void DFS(Graph G,int v){     //从顶点v出发，深度优先遍历图Gvisited [v]=TRUE;        //设已访问标记for(w=FirstNeighbor(G,v);w>=0 ; w=NextNeighor(G,v,w))if(!visited[w]){     //w为u的尚未访问的邻接顶点DFS(G,w);}//ifprint(v);                //输出顶点
}

6.4.5 关键路径

AOE 网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 AOE 网 (Activity On Edge NetWork)。

AOE网具有以下两个性质：
①只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；
②只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。
在 AOE 网中仅有⼀个入度为 0 的顶点，称为开始顶点（源点），它表示整个⼯程的开始；也仅有⼀个出度为 0 的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。

在AOE网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

寻找冠军活动时所用到的几个参量的定义：

1. 事件 vk的最早发生时间 ve(k)：决定了所有从vk 开始的活动能够开工的最早时间。
2. 事件 vk的最迟发⽣时间 vl(k)：它是指在不推迟整个工程完成的前提下，该事件最迟必须发⽣的时间。
3.活动ai的最早开始时间e(i)：指该活动弧的起点所表示的事件的最早发生时间。
4.活动ai的最迟开始时间l(i)：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
5.活动 ai的时间余量d(i)=l(i)−e(i)，表示在不增加完成整个⼯程所需总时间的情况下，活动ai可以拖延的时间若⼀个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0 即l(i)=e(i) 的活动ai是关键活动，由关键活动组成的路径就是关键路径。

求关键路径的步骤：
1.求所有事件的最早发生时间ve():按拓扑排序序列，依次求各个顶点的ve(k)， ve(源点)=0， ve(k) =Max{vef)+W eight(vj , vk )}，vj为vk的任意前驱。
2.求所有事件的最迟发生时间vl():按逆拓扑排序序列，依次求各个顶点的 vl(k)，vl(汇点)= ve(汇点)，vl(k)=Min{vl(j)- W eight(vk , vi)}，v为Vv\k 的任意后继。
3.求所有活动的最早发生时间e():若边<Vk ,Vj>表示活动a;，则有e(i)=ve(k)。
4.求所有活动的最迟发生时间1():若边<Vk,Vj >表示活动a，则有l(i)= vl(j)- Weight(vi , vj)。
5.求所有活动的时间余量d(): d(i)= l(i)-e(i)。

关键活动、关键路径的特性:
1.若关键活动耗时增加，则整个工程的工期将增长。
2.缩短关键活动的时间，可以缩短整个工程的工期。
3.当缩短到一定程度时，关键活动可能会变成非关键活动。
4.可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。