【王道数据结构】第六章(下) | 图的应用
目录
一、最小生成树
二、最短路径
三、有向⽆环图描述表达式
四、拓扑排序
五、关键路径
一、最小生成树
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算法
- BFS算法的局限性：BFS算法求单源最短路径只适⽤于⽆权图，或所有边的权值都相同的图。
- Dijkstra算法能够很好的处理带权图的单源最短路径问题，但不适⽤于有负权值的带权图。
- 使用 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算法
-
Floyd算法：求出每⼀对顶点之间的最短路径，使⽤动态规划思想，将问题的求解分为多个阶段。
-
Floyd算法可以⽤于负权值带权图，但是不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径。
-
Floyd算法使用到两个矩阵：
dist[][]：目前各顶点间的最短路径。path[][]：两个顶点之间的中转点。
-
代码实现：
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⽹具有以下两个性质：
- 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；
- 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。 另外，有些活动是可以并⾏进⾏的。
3.在 AOE ⽹中仅有⼀个⼊度为 0 的顶点，称为开始顶点（源点），它表示整个⼯程的开始； 也仅有⼀个出度为 0 的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。
- 从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动。
- 完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个 ⼯程的完成时间就会延⻓。