C语言详细分析贪心策略中最小生成树的Prime算法设计与实现

浅析最小生成树

设G=(V,E)是无向连通带权图。E中每条边(v,w)的权为c[v][w]。

生成树：如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。

耗费：生成树上各边权的总和

最小生成树：在G的所有生成树中，耗费最小的生成树最小生成树在实际中有广泛应用。

例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出建立通信网络的最经济的方案。

Prime算法思想

牵扯到贪心策略

设G=(V，E)是无向连通带权图，V={1,2,…,n}；

设最小生成树T=(U，TE)，算法结束时U=V，TE E。

首先，令U={u0}，TE={}。然后，只要U是V的真子集，就做如下贪心选择：选取满足条件i U，j V-U，且边(i，j)是连接U和V-U的所有边中的最短边，即该边的权值最小。然后，将顶点j加入集合U，边(i，j)加入集合TE。继续上面的贪心选择一直进行到U=V为止，此时，选取到的所有边恰好构成G的一棵最小生成树T。需要注意的是，贪心选择这一步骤在算法中应执行多次，每执行一次，集合TE和U都将发生变化，即分别增加一条边和一个顶点。

此算法核心部分

结构体的选择

选择一个合适的数据结构可以让程序的实现效率大大提高，难度大大降低；既然是生成最小生成树，不妨选择点和边结构体；因此创建两个结构体，第一个点node结构体包含所有的结点；第二个边结构体包含所有待选择的边、连接点及权值。

实现思路

tips:onTreet 属性是布尔类型，为true时该结点在“树”上

首先对应第一个结点找我们需要的边，我们需要什么样的边呢，那就是在边的两个连接点中，有且仅有一个连结点等于结点的名称（这个可以在点结构体中加ID属性），并且这个结点必须是根结点（即onTree为true），满足这个条件，就把另一个连接点的onTree属性设为true；最后为了把满足条件的边连起来，我就个边结构体也加一个onTree属性，输出所有onTree 为true的边结构体即可。

构造实例

按Prim算法对如图所示的无向连通带权图构造一棵最小生成树。

构造过程

点和边结构体数组图示如上所示，我们需要的最终效果为下图所示：

代码详解

#include <iOStream>
using namespace std;
struct Node {
	int ID;//结点序号
	bool OnTree;//是否属于最小生成树
};
struct LS {
	int N1, N2; int V; bool OnTree;//OnTree用于判断此边是否在“树”上
	LS(int n1, int n2, int v) {
		N1 = n1; N2 = n2; V = v; OnTree = false;//N1,N2为边左右连接点，v是边的权值
	}
};
Node A[] = { {1,false}, {2,false}, {3,false}, {4,false}, {5,false} };//点结构体数组
LS L[8] = { LS(1,2,1),LS(1,3,4) ,LS(2,3,2),
LS(2,5,2),LS(4,5,4),LS(3,4,6),LS(3,5,3),LS(1,4,8)};//边结构体数组
bool FindOne(LS L ,Node A[]) {//布尔类型
	int m = 0;
	for (int i = 0; i < 5; i++)
		if (L.N1 == A[i].ID && A[i].OnTree) m++;
	for (int i = 0; i < 5; i++)
		if (L.N2 == A[i].ID && A[i].OnTree) m++;
	return m ==1;//只有N1和N2的一个连接到了在“树”上的结点才为真
}
int main()
{
	A[0].OnTree = true;
	for (int i = 0; i < 5; i++) {
		int p = 0;
		for (int j = 0; j < 8; j++) {
			if (FindOne(L[j], A)) {
				p = j; break;
			}
		}
		for (int i = 0; i < 8; i++) {
			if (FindOne(L[i], A))
				if (L[i].V < L[p].V) p = i;
		}
		L[p].OnTree = true;//选中的边设置为在“树”上
        //将边的连接点放在“树”上
		for (int i = 0; i < 5; i++) {
			if (L[p].N1 == A[i].ID) A[i].OnTree = true;
			if (L[p].N2 == A[i].ID) A[i].OnTree = true;
		}
	}
    //输出最小生成树所有边
	for (int i = 0; i < 8; i++) {
		cout << L[i].OnTree;
	}
}

结构体node 和结构体LS在上文已经较为详细的介绍了，而且还给出了node数组A和LS数组L的图示，不过要注意默认的边都是不在“树”上的；

主函数一共有四个for循环，最后一个for循环仅仅就是为了输出在最小生成树上的边，和prime的核心没有关系；

第一个for循环也就是最大的for循环，用来确定生成最小生成树的找边次数；

第二个for循环是为了找出我们所需要的边，如果存在一条边，有且仅有一个连结点等于结点的名称并且该连接点是在“树”上的，那么返回改边下标并用变量p记录；

第三个for循环是为了筛选出所有满足此条件边中权值最小的边，并把该边的小标用p记录；将最终选出的边放在“树”上，利用第三个for循环把与该边连接的点都放在“树”上，然后循环执行上述过程，直到没有满足条件的边，大循环结束，输出最小生成树。

这里详细的解析一下FindOne函数：

bool FindOne(LS L ,Node A[]) {//布尔类型
	int m = 0;
	for (int i = 0; i < 5; i++)
		if (L.N1 == A[i].ID && A[i].OnTree) m++;
	for (int i = 0; i < 5; i++)
		if (L.N2 == A[i].ID && A[i].OnTree) m++;
	return m ==1;//只有N1和N2的一个连接到了在“树”上的结点才为真
}
//调用方法 ： FindOne(L[j], A)

调用该函数的时候，实参第一个是边结构体类型的L数组内的任意一个元素，第二个则是点结构体类型的A数组的首地址，所以形参第一个需要传入LS类型的变量L，第二个则是整个Node类型的数组，这样传参才相互对应，如果对于函数传参有疑问，可以参考这篇函数的传参方式然后定义变量m初始值为0，第一个for循环是和该边的第一个连接点作比较，满足条件则m+1；第二个for循环是和该边第二个连接点作比较，满足条件也会加m也会加1；但是我只要比较结果为一的m，这样就能筛选出满足条件的边。

调试结果

第一次循环，满足条件的最小权值边下标应为0（p为0），初始值第一个结点默认放在“树”上；由于p为0，所以第一个边的两个连接点都会被放在“树”上；（ID1和2都是true）

第二次循环，p为2，数组中第三条边左右连接点对应的ID2和3都会变为true；

​​​​​​第三次循环，p为3，同理，ID5会变成true；

接下来重复上面的过程，直到没有满足条件的边，循环结束；

最后就是输出所有在“树”上的边了，数组中为1的边就是被选中的边，这样清晰的得到了最终的最小生成树了。

总结

Prime算法属于贪心算法的一种，尽情的找到权值最小的边并连接到一起，最小生成树的算法分享与实现圆满完成了，希望对大家有实质性的帮助

到此这篇关于C语言详细分析贪心策略中最小生成树的Prime算法设计与实现的文章就介绍到这了,更多相关C语言Prime算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！