最小生成树（带权无向图）

迈不过友情╰ 2022-05-27 07:42 182阅读 0赞

在一个无向图中找出一棵最小生成树：

一个无向图G的最小生成树就是由该图的那些连接G的所有顶点的边构成的树，且其总价值最低，最小生成树存在当且仅当G是连通的。在最小生成树中边的条数是|V|-1，并且无圈。

对于任一个生成树T，如果将一条不属于T的边e添加进来，则产生一个圈。如果从该圈中除去任意一条边，则又恢复生成树的特性。如果边e的值比除去的边的值低，那么新的生成树的值就比原生成树的值低。如果在建立生成树时添加的边在所有避免成圈的边中值最小，那么最后得到的生成树的值不能再改进，因为任意一条替代的边的值都大于等于已存在于该生成树中的一条边的值，它指出，对于最小生成树这种贪欲是成立的。下图是图G与它的最小生成树。

![20180414103342256][]

利用Prim算法计算最小生成树：

计算最小生成树的一种方法是使其连续的一步步长成。在每一步，都要把一个节点当做根并往上加边，这样也就把相关联的顶点加到增长的树上。

在算法的任意时刻，我们都可以看到一个已经添加到树上的顶点集，而其余顶点尚未加到这棵树上。此时，算法在每一阶段都可以通过选择边（u，v），使得（u，v）的值是所有u在树上但v不在树上的值中的最小者，而找出一个新的顶点并把它添加到这棵树中。下图指出该算法如何从v1开始构建最小生成树。开始时，v1在构建中的树上，它做为树的根但是没有边。每一步添加一条边和一个顶点到树上。

![20180414111347569][]

由此可得出生成树的边为：（v2，v1）、（v3，v4）、（v4，v1）、（v5，v7）、（v6，v7）、（v7，v4），生成树总的价值是16。

程序如下：

#include<iostream>
    #include<assert.h>
    #include<string>
    #include<limits.h>
    
    #define NUM 7
    using namespace std;
    
    //利用二维数组创建有向图的邻接矩阵
    void CreateMatrix(int mat[NUM][NUM]);
    //利用Prim算法求解最小生成树
    void DijkstraSearch(int mat[NUM][NUM], int i, int visit[NUM], int dist[NUM], int path[NUM]);
    
    int main()
    {
    	//创建有向图的带有权值的邻接矩阵
    	int mat[NUM][NUM];
    	for (int i = 0; i < NUM;i++)
    	{
    		for (int j = 0; j < NUM;j++)
    		{
    			mat[i][j] = INT_MAX;
    		}
    	}
    	CreateMatrix(mat);
    	int visit[NUM] = {0};
    	int dist[NUM];
    	for (int i = 0; i < NUM;i++)
    	{
    		dist[i] = INT_MAX;
    	}
    	int path[NUM] = {0};
    	
    	//利用Prim算法求解最小生成树
    	//初始源点的dist初始化为0，path初始化为0
    	dist[0] = 0;
    	path[0] = 0;
    	DijkstraSearch(mat,0,visit,dist,path);
    
    	//输出最小生成树的边及相应权值，总权值
    	int totalValue = 0;
    	for (int i = 1; i < NUM;i++)
    	{
    		totalValue += dist[i];
    		printf("最小生成树的边：<v%d , v%d>",(i+1),(path[i]+1));
    		printf(" 权值：%d",dist[i]);
    		printf("\n");
    	}
    	printf("最小生成树的总权值：%d",totalValue);
    	printf("\n");
    
    	return 0;
    }
    
    
    //利用二维数组创建有向图的邻接矩阵，带权值
    void CreateMatrix(int mat[NUM][NUM])
    {
    	mat[0][1] = 2;
    	mat[0][2] = 4;
    	mat[0][3] = 1;
    
    	mat[1][0] = 2;
    	mat[1][3] = 3;
    	mat[1][4] = 10;
    
    	mat[2][0] = 4;
    	mat[2][3] = 2;
    	mat[2][5] = 5;
    
    	mat[3][0] = 1;
    	mat[3][1] = 3;
    	mat[3][2] = 2;
    	mat[3][4] = 7;
    	mat[3][5] = 8;
    	mat[3][6] = 4;
    
    	mat[4][1] = 10;
    	mat[4][3] = 7;
    	mat[4][6] = 6;
    
    	mat[5][2] = 5;
    	mat[5][3] = 8;
    	mat[5][6] = 1;
    
    	mat[6][3] = 4;
    	mat[6][4] = 6;
    	mat[6][5] = 1;
    }
    
    //利用Prim算法求解最小生成树
    void DijkstraSearch(int mat[NUM][NUM], int i, int visit[NUM], int dist[NUM], int path[NUM])
    {
    	//初始化
    	visit[i] = 1;
    	//dist[i] = 0;
    	//path[i]=0;
    
    	//访问与顶点i相邻接的未被访问的顶点，获取路径长度，如果小于之前路径长度则替换，并记录路径
    	for (int j = 0; j < NUM;j++)
    	{
    		if (visit[j] == 0 && mat[i][j] != INT_MAX)
    		{
    			if (mat[i][j]<dist[j])
    			{
    				dist[j] = mat[i][j];
    				path[j] = i;
    			}
    		}
    	}
    
    	//在未被访问过的顶点中寻找路径最短的顶点
    	int minDist = -1;
    	for (int m = 0;m<NUM;m++)
    	{
    		if (visit[m] == 0)
    		{
    			minDist = m;
    			break;
    		}
    	}
    	for (int k = minDist + 1; k<NUM; k++)
    	{
    		if (visit[k] == 0 && dist[k]<dist[minDist])
    		{
    			minDist = k;
    		}
    		
    	}
    	//如果找到继续寻找到下一个顶点的最短路径（递归）
    	if (minDist != -1)
    	{
    		DijkstraSearch(mat, minDist, visit, dist, path);
    	}
    }

结果如下：

![20180414111836637][]

[20180414103342256]: /images/20220527/627cfcb132a7492abc894de7ee27a49b.png
[20180414111347569]: /images/20220527/b4ac4c1b125646e599652bd60d3765d1.png
[20180414111836637]: /images/20220527/d107dc2324ba4797bb27fac12cc17cfd.png