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

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;               //中转点
                }
			}
        }
    }

6.4.3 有向无环图描述表达式

6.4.4拓扑排序