【王道数据结构】第六章(下) | 图的应用

目录

一、最小生成树

二、最短路径

三、有向⽆环图描述表达式

四、拓扑排序

五、关键路径

---

一、最小生成树

1、最小生成树的概念

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

• 最小生成树可能有多个，但边的权值之和总是唯一且最小的。
• 最小生成树的边数 =顶点数 -1。砍掉一条则不连通，增加一条边则会出现回路。
• 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。
• 只有连通图才有生成树，非连通图只有生成森林。

2、求最小生成树的两种方法

• Prim算法
• Kruskal算法 

Prim算法(普里姆)：从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。时间复杂度: O(V2)适合用于边稠密图

Kruskal算法(克鲁斯卡尔)：每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)直到所有结点都连通。时间复杂度: O(lEllog2lEl )适合用于边稀疏图

二、最短路径

1.无权图的单源最短路径问题——BFS算法

使用 BFS算法求无权图的最短路径问题，需要使用三个数组

• d[]数组用于记录顶点 u 到其他顶点的最短路径。
• path[]数组用于记录最短路径从那个顶点过来。
• visited[]数组用于记录是否被访问过。

代码时间

#define MAX_LENGTH 2147483647			//地图中最大距离，表示正无穷// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){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]){d[w]=d[u]+1;path[w]=u;visited[w]=TREE;EnQueue(Q,w);			//顶点w入队}}}
}

2.单源最短路径问题——Dijkstra算法

1. BFS算法的局限性：BFS算法求单源最短路径只适⽤于⽆权图，或所有边的权值都相同的图。
2. Dijkstra算法能够很好的处理带权图的单源最短路径问题，但不适⽤于有负权值的带权图。
3. 使用 Dijkstra算法求最短路径问题，需要使用三个数组：

• final[]数组用于标记各顶点是否已找到最短路径。
• 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;}}}
}

3.各顶点间的最短路径问题——Floyd算法

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

2. Floyd算法可以⽤于负权值带权图，但是不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径。

3. Floyd算法使用到两个矩阵：

   1. dist[][]：目前各顶点间的最短路径。
   2. path[][]：两个顶点之间的中转点。

4. 代码实现：

int dist[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];void Floyd(MGraph G){int i,j,k;// 初始化部分for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){dist[i][j]=G.Edge[i][j];		path[i][j]=-1;}}// 算法核心部分for(k=0;k<G.vexnum;k++){for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(dist[i][j]>dist[i][k]+dist[k][j]){dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}}}}
}

4.最短路径算法比较：

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

三、有向⽆环图描述表达式

1.有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称 DAG图（Directed Acyclic Graph）。

DAG描述表达式：((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

2.有向无环图描述表达式的解题步骤：

• Step 1:把各个操作数不重复地排成一排
• Step 2:标出各个运算符的生效顺序 (先后顺序有点出入无所谓)
• Step 3:按顺序加入运算符，注意“分层”
• Step 4:从底向上逐层检查同层的运算符是否可以合体

四、拓扑排序

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

2.拓扑排序：在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：

• 每个顶点出现且只出现⼀次；
• 若顶点 A 在序列中排在顶点 B 的前⾯，则在图中不存在从顶点 B 到顶点 A 的路径。
• 或定义为：拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后⾯。每个 AOV ⽹都有⼀个或多个拓扑排序序列。
   

3.拓扑排序的实现:

• 从AoV网中选择一个没有前驱 (入度为0) 的顶点并输出
• 从网中删除该顶点和所有以它为起点的有向边。
• 重复D和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止

4.代码实现拓扑排序（邻接表实现）：

#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;				//排序成功
}

五、关键路径

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

2.AOE⽹具有以下两个性质：

1. 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。 另外，有些活动是可以并⾏进⾏的。

3.在 AOE ⽹中仅有⼀个⼊度为 0 的顶点，称为开始顶点（源点），它表示整个⼯程的开始； 也仅有⼀个出度为 0 的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。

• 从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动。
• 完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个 ⼯程的完成时间就会延⻓。