贪心算法——最小生成树Prim算法

最小生成树Prim算法

最小生成树(MST)是图论当中一个重要的算法,在实际生活中具有广泛的应用。有多种算法可以解决最小生成树问题,这里讲解Prim算法

问题描述

​在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边,而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集且为无循环图,使得的 w(T) 最小,则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。

分析设计

Prim算法是解决最小生成树问题的经典算法之一。

其主要思想为:

  1. 出发;从图G中找到一个点a作为起始点(不一定是最终最小生成树的树根),加入到MST集合中;
  2. 从与a相邻的顶点中选出权值最小的边,对应点为顶点b,将b也加入到MST中。这样就找到了一组最小生成树的邻接边(树枝);
  3. 不断在G-MST集合(即剩余顶点)中的找到一个顶点v,使得v到MST集合中任意一点的权值最小,将v加入MST中;
  4. 重复第3步,直至所有点都在MST中。此时,最小生成树就建好了。

贪心算法——最小生成树Prim算法

gif制作来源于VisuAlgo https://visualgo.net/zh/sorting

现在我们就大致知道了Prim算法的基本思路,接下来就是具体实现。

  1. 我们采用二位数组邻接矩阵的数据结构来储存图的相关信息;最小生成树采用结构体数组的形式存储:存储顶点a,顶点b,邻接边权值w;

  2. 构造数组MINedge[n]MINedge[n]MINedge[n],其中n为顶点数。MINedge[i]MINedge[i]MINedge[i]表示顶点i到MST集合中任意一点的最小权值;MINedge[i]=1MINedge[i]=-1MINedge[i]=−1表示顶点i在MST中。
    贪心算法——最小生成树Prim算法
    如在此图中,此时,点v1为最小生成树的顶点(即v1在MST中),则MINedge[2]=2MINedge[3]=4MINedge[4]=1MINedge[1]=1MINedge[2]=2、MINedge[3]=4、MINedge[4]=1、MINedge[1]=-1MINedge[2]=2、MINedge[3]=4、MINedge[4]=1、MINedge[1]=−1;

  3. 构造mst[n]mst[n]mst[n]数组,其中n为顶点数。mst[i]mst[i]mst[i]对应MINedge[i]MINedge[i]MINedge[i],表示顶点iii和顶点mst[i]mst[i]mst[i]的邻接边为MINedge[i]MINedge[i]MINedge[i]。mst[i]=0mst[i]=0mst[i]=0表示顶点i在MST中。
    如在上图中,mst[1]=0mst[2]=1mst[3]=1mst[4]=1mst[1]=0、mst[2]=1、mst[3]=1、mst[4]=1mst[1]=0、mst[2]=1、mst[3]=1、mst[4]=1;

  4. 构造完成。从顶点1出发;

  5. 遍历MINedge找出最小值w,以及对应的顶点a(数组下标),找出对应的mst数组中对应的顶点b。这样最小生成树的一根树枝就找到了。将a,b,w的信息放入最小生成树的数组中保存。将MINedge[a]MINedge[a]MINedge[a]置为-1,mst[a]mst[a]mst[a]置为0;

  6. 因为MST中又加入了一个顶点,因此要更新MINedge数组:将a的邻接边权值与MINedge中对应顶点的值比较,保留小的值,同时若更新了MINedge也要更新mst

  7. 重复第5步,直到所有顶点都在MST中。最小生成树构造完成。

源代码

#include <iostream>
#include <vector>
using namespace std;

//最小生成树
typedef struct Tree {
	int vexa;
	int vexb;
	int edge;
};
vector<Tree> tree;

int prim(vector<vector<int> > &g) {
	int vex = g.size() - 1;		//顶点个数
	int cost = 0;	//最终生成树权值
	vector<int> mst(vex + 1);	//MST[i]表示顶点i连到MST中的哪个顶点,值=0时表示在MST中
	vector<int> MINedge(vex + 1);	//顶点i的邻接边中的最小值,值=-1时表示在MST中

	mst[1] = 0;	//将点1放入MST
	for (int i = 1; i <= vex; i++) {
		MINedge[i] = g[1][i];
		mst[i] = 1;
	}

	for (int i = 2; i <= vex; i++) {
		int MINvex = 0;		//最小边顶点
		int MINcost = INT_MAX;	//最小权值

		for (int j = 2; j <= vex; j++) {
			if (MINedge[j] < MINcost && MINedge[j] != -1) {	//最小边顶点不在MST中(两个顶点不能都在MST中)
				MINvex = j;
				MINcost = MINedge[j];
			}
		}
		Tree t;	//将点放入MST中
		t.vexa = mst[MINvex];
		t.vexb = MINvex;
		t.edge = MINcost;
		tree.push_back(t);
		cost += MINcost;
		MINedge[MINvex] = -1;

		//更新MINedge
		for (int i = 2; i <= vex; i++) {
			if (g[MINvex][i] < MINedge[i]) {
				MINedge[i] = g[MINvex][i];
				mst[i] = MINvex;
			}
		}
	}

	return cost;
}

int main() {
	//初始化图
	int vexNum, edgeNum;
	cout << "输入顶点个数、边数:";
	cin >> vexNum >> edgeNum;
	vector<vector<int> > graph(vexNum + 1, vector<int>(vexNum + 1, INT_MAX));
	cout << "输入邻接边及权值a b w" << endl;
	int a, b, w;
	for (int i = 0; i < edgeNum; i++) {
		cin >> a >> b >> w;
		graph[a][b] = w;
		graph[b][a] = w;
	}
	for (int i = 1; i <= vexNum; i++)
		graph[i][i] = 0;

	int cost = prim(graph);	//prim算法

	cout << endl << "最小生成树组成:" << endl;
	for (int i = 0; i < tree.size(); i++) {
		cout << tree[i].vexa << " -> " << tree[i].vexb << " = " << tree[i].edge << endl;
	}
	cout << "总权值为:" << cost << endl;

	system("pause");
	return 0;
}
/*
1 2 2
1 3 4
1 4 1
2 4 3
2 5 10
3 4 2
3 6 5
4 5 7
4 6 8
4 7 4
5 7 6
6 7 1
*/

运行结果

贪心算法——最小生成树Prim算法
贪心算法——最小生成树Prim算法

上一篇:XYNU1393: 最短网络Agri-Net(prim)


下一篇:Prim算法