王道数据结构6.2(图的应用)
图的应用
- 一、最小生成树
- (一)什么是最小生成树?
- (二)求最小生成树算法
- (1)prim算法
- (2)Kruskal算法(克鲁斯卡尔)
- 二、最短路径问题
- (一)单源最短路径问题
- (1)BFS算法(无权图)
- (2)Dijkstra算法(带权图、无权图)
- (二)多源最短路径问题— Floyd算法(带权图、无权图)
一、最小生成树
(一)什么是最小生成树?
- 对于一个带权连通无向图G=(V,E),生成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合,若T为R中边的权值之和最小的生成树,则T称为G的最小生成树。
- 一个连通图的生成树包含图的所有的顶点,并且只尽可能少的边,对于生成树而言,若砍去它的一条边,则生成树变成非连通图,若给它增加一条边,则会形成图中的一条回路。
- 只有连通图才有生成树,非连通图只有生成森林。
- 如果一个连通图本身就是一棵树,则其最小生成树就是它本身。
- 最小生成树不是唯一的,但是当各个边的权值互不相同时,最小生成树是唯一的,若无向连通图的边数比顶点少1,即本身就是一个树,则最小生成树就是它自身。
- 最小生成树的权值总和却是唯一的,是最小的。
(二)求最小生成树算法
- 都是基于贪心算法的策略。
- 总体思路:确定顶点集合中有关的边,寻找到最小代价边(u,v),判断加入集合后会不会产生回路,若不会,则为最小生成树的一员。
(1)prim算法
- 思路:从某一个顶点开始构建生成树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止。
int dist[n],state[n],pre[n];
dist[1] = 0;
for(i : 1 ~ n)
{
t <- 没有连通起来,但是距离连通部分最近的点;
state[t] = 1;
更新 dist 和 pre;
}
- 时间复杂度:O(|V|2),适合于稠密图。
- 算法实现,以图示为例:
(1)首先从V0开始,构建两个表,分别是isjoin[]:记录各个结点是否已经加入树,初始时,v0为true,其他为false;lowCost[]:各个节点加入树的最低代价。
(2)如图所示:lowCost数组的意思:小集团中只有v0存在的情况下,v1到v0最少需要6,v2到v0需要5,v3需要1,而v45没有连通,为∞。
(3)对比lowCost数值,得到v3最小,则修改isjoin[3]=true,并且将lowCost更新为:v1可以于v3连通为5,5<6,则改为5,v2可以有4/5,则填入4,v3仍为1,v4为6,v5为4,总之lowCost为054164,扫描一遍lowCost数组选择false中最小的,即v2/v5。
(4)重复以上过程,直到isjoin所有都变成true。
(2)Kruskal算法(克鲁斯卡尔)
- 思路:每次选择一条权值最小的边,使者条边的两头连通(原本连通的就不选),直到所有结点都连通。
- 时间复杂度:O(|E|log2|E|),适用于边稀疏图。
- 算法实现过程:
(1)如图所示,首先对所有的边进行大小排序
(2)第一轮:检查第一条边的两个顶点是否连通(是否属于同一个集合,意思是,初始的时候所有顶点都是独自成为一个集合,都不互相连通,当选取顶点以后,被选择的顶点就属于一个集合,并且连在一起,其他顶点保持不变),如果顶点不是一个集合,则选择存入被选中集合,即选择(v0,v3)(v2,v5)(v1,v4)(v2,v3)而到(v3,v5)时,由于借助v2实现了连通,则跳过不建立集合,如下图所示,类似的后序寻找
(3)一共需要执行e轮,每轮判断两个顶点是否属于同一个集合,需要O(log2e),总时间复杂度为O(elog2e)
二、最短路径问题
(一)单源最短路径问题
(1)BFS算法(无权图)
- 类似于广度优先遍历算法
- 代码:
#include <stdio.h>
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
int Max = 0x3f3f3f3f;
typedef struct {
VertexType Vex[MaxVertexNum];
EdgeType EdgeType[MaxVertexNum][MaxVertexNum];
int vexnum, arcnum;
} Gragh;
//BFS遍历
bool visited[MaxVertexNum];
void BFSTraverse(Graph G) {
for (int i = 0; i < G.vexnum; ++i)
visited[i] = false;
InitQueue(Q);
for (int i = 0; i < G.vexnum; ++i)
if (!visited[i])
BFS(G, i);
}
void BFS(Graph G, int v) {
visit(v);
visited[v] = true;
Enqueue(Q, v);
while (!isEmpty(Q)) {
DeQueue(Q, v);
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
if (!visited[w]) {
visit(w);
visited[w] = true;
EnQueue(Q, w);
}
}
}
//BFS求单源最短路径
void BFS_MIN_Distance(Graph G, int u) {
//d[i]表示从u到i结点的最短路径
for (int i = 0; i < G.vexnum; i++){
d[i] = Max; //初始化路径为无穷
path[i]=-1;//最短路径从哪个顶点过来
}
visited[u] = true;
d[u] = 0;
EnQueue(Q, u);
while (!isEmpty(Q)) {
DeQueue(Q, u);//队头元素u出队
for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))//找到和它相邻的所有结点+
if (!visited[w]) {//w为u的尚未访问的邻接顶点
visited[w] = true;//设已访问的标记
d[w] = d[u] + 1;//路径长度+1
path[w]=u;//最短路径应该是从u到v
EnQueue(Q, w);//顶点w入队
}//if
}//while
}
- 过程:从2号顶点开始
① 首先初始化d和path和visited数组
队列:NULL
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|
d[] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
path[] | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
visited[] | false | false | false | false | false | false | false | false |
② 修改起始节点的数组,并且将2结点压入队列中
队列:2
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|
d[] | ∞ | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
path[] | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
visited[] | false | true | false | false | false | false | false | false |
③ 非空进入while循环,取出队首元素2,判断与2相连的所有结点:1,6,1结点的visited为false,1的d[]数组改为1+d[2],并且path[1]=2,表示与结点2距离为1,并且最短路径中前驱是2,并且将1压入队列;6号结点同理,6的d[]数组改为1+d[2]=1,并且path[6]=2,visited[6]=true,并且将6压入队列
队列:1、6
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|
d[] | ∞ | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
path[] | -1 | -1 | -1 | -1 | -1 | 1 | -1 | -1 |
visited[] | false | true | false | false | false | true | false | false |
④ 取出队首1,判断1的连通未访问的顶点为5,则5的d[5]改为d[1]+1=1+1=2,path[5]=1,visited[5]=1,入队
队列:6、5
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|
d[] | ∞ | 0 | ∞ | ∞ | 2 | ∞ | ∞ | ∞ |
path[] | -1 | -1 | -1 | -1 | 1 | 1 | -1 | -1 |
visited[] | false | true | false | false | true | true | false | false |
⑤ 判断6 判断5即可得到
队列:1、6
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
---|---|---|---|---|---|---|---|---|
d[] | 1 | 0 | 2 | 3 | 2 | 1 | 2 | 3 |
path[] | 2 | -1 | 6 | 3 | 1 | 2 | 6 | 7 |
visited[] | true | true | true | true | true | true | true | true |
得到上述表格,问2到8的路径=d[8]=3,路径逆向思维进行寻找,8前为7,7前为6,6前为2,得到:2->6->7->8
4. 分析:广度优先生成树其实层数就反映了到达其他节点的最短路径,换句话说,利用广度优先构造的最小生成树,高度一定是最小的。
(2)Dijkstra算法(带权图、无权图)
- BFS算法的局限性:BFS算法只适合于不带权或带权值都相同的情况,如果带权权值不同则会出现错误。
- 过程:
① 初始化三个数组:final[] (标记各顶点是否已找到最短路径)、dist[] (最短路径长度)、path[](路径上的前驱)。
v0 | v1 | v2 | v3 | v4 | |
---|---|---|---|---|---|
final[] | √ | × | × | × | × |
dist[] | 0 | 10 | ∞ | ∞ | 5 |
path[] | -1 | 0 | -1 | -1 | 0 |
如图所示:当前可以确定的是v0可以到v4,可以到v1,分别是5,10,写入数组,并且修改path1,4的前驱为0 。
② 第一轮,循环遍历所有结点,找到目前还没有确定最短路径,且dist最小的顶点v,令final[i]=ture。如本题,最小dist为4的5,即可以说明v0到v4的最短路径为5,修改final[4]=√,并且检查所有和v4相邻的顶点,寻找有没有可能v0经过v4到其他点路径更近,发现v0v4v1长度为5+3=8<10=v0v1,所以让dist[1]=8,同理dist[2]=5+9=14,path[2]=4,dist[3]=7,path[3]=4。
v0 | v1 | v2 | v3 | v4 | |
---|---|---|---|---|---|
final[] | √ | × | × | × | √ |
dist[] | 0 | 8 | 14 | 7 | 5 |
path[] | -1 | 4 | 4 | 4 | 0 |
③第二轮,随后检查所有final值为false的顶点的,发现目前dist最小的是7,则处理3顶点,让final为√,表示已经可以确定v0->v3最短为7,且路径为0->4->3,然后检查所有v0经过v3到达的顶点vi,修改得
v0 | v1 | v2 | v3 | v4 | |
---|---|---|---|---|---|
final[] | √ | × | × | √ | √ |
dist[] | 0 | 8 | 13 | 7 | 5 |
path[] | -1 | 4 | 3 | 4 | 0 |
④ 检查所有final值为×的结点,选择1,更新后检查v4,v2,因为v4之前已经确定了,所以无需检查只要看v2即可,
⑤ 一直到final值全部为√。
v0 | v1 | v2 | v3 | v4 | |
---|---|---|---|---|---|
final[] | √ | √ | √ | √ | √ |
dist[] | 0 | 8 | 9 | 7 | 5 |
path[] | -1 | 4 | 1 | 4 | 0 |
- 分析
(1)代码思路:以从v0开始为例,初始时
final[0]=ture;dist[0]=0;path[0]=-1;
final[k]=false;dist[k]=arcs[0][k];path[k]=(arcs[0][k]==∞)?-1:0;
(2)需要经过n-1轮循环,循环遍历所有结点,找到还没有确定最短路径,且dist最小的顶点vi,令final[i]=true。检查所有邻接自vi的顶点,对于邻接自vi的顶点vj,若final[j]==false且dist[i]+arcs[i][j]<dist[j],则令dist[j]=dist[i]+dist[i][j],path[j]=i。
(3)时间复杂度:由于每一轮都要扫描所有数组,数组长度为n顶点个数,并且还要扫描邻接矩阵,则O(2n)~O(n),因为要扫描n-1轮,则时间复杂度为O(n(n-1)~O(n2)
(4)和prim算法很是相似,时间复杂度也是相似的
(5)注意:如果带权图中权值有负数,则这个算法将会出错,不适用。