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); //队头元素出队并赋给u
for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
if(!visited[w]){ //w为u的尚未访问的邻接顶点
d[w]=d[u]+1; //路径长度＋1
path[w]=u; //最短路径应从u到w
visited[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;
else
path[i]=u;
final[u]=TREE;
}
for(int i=0; i<G.vexnum; i++){
int MIN=MAX_LENGTH;
int v;
// 循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点v
for(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和path
for(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; //中转点
}
}
}
}
