趣学算法-贪心：最小生成树

痛定思痛。 2022-05-04 03:56 192阅读 0赞

校园网是为学校师生提供资源共享、信息交流和协同工作的计算机网络。校园网是一个 宽带、具有交互功能和专业性很强的局域网络。如果一所学校包括多个学院及部门，也可以 形成多个局域网络，并通过有线或无线方式连接起来。原来的网络系统只局限于以学院、图书馆为单位的局域网，不能形成集中管理以及各种资源的共享，个别学院还远离大学本部， 这些情况严重地阻碍了整个学校的网络化需求。现在需要设计网络电缆布线，将各个单位的 局域网络连通起来，如何设计能够使费用最少呢？

![70][]

![70 1][]

![70 2][]

![70 3][]

> 贪心策略：选取连接U和V-U的所有边的最短边。

![70 4][]

![70 5][]

> 第一步：对closset、s、lowcost，c数组初始化

closest\[j\]:表示V-U中的顶点j到集合U中的最邻近点；

lowcost\[j\]:表示V-U中的顶点j到集合U中的最邻近点的边值，即边（j, closest\[j\]）的权值

s\[i\]:s\[i\]==true，表示顶点i在U集合中。

代码示例：

对c\[i\]\[j\]进行初始化（c\[i\]\[j\]表示连接顶点i和j的边的权值）

cout << "输入结点数n和边数m: " << endl;
    	cin >> n >> m;
    	
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(i == j) c[i][j] = 0;
    			else c[i][j] = INF;
    		}
    	}
    	
    	cout << "输入结点数u、v和边值w: " << endl;
    	for(int i = 1; i <= m; ++ i)
    	{
    		cin >> u >> v >> w;
    		c[u][v] = c[v][u] = w; 
    	}

初始化其余三个数组。

s[u0] = true;//初始时，集合中只有U一个元素，即顶点u0；
    	int i;
    	int j;
    	
    	//初始化 
    	for(i = 1; i <= n; ++i)
    	{
    		if(i != u0)
    		{
    			lowcost[i] = c[u0][i];
    			closest[i] = u0;
    			s[i] = false;
    		}
    		else
    			lowcost[i] = 0;
    	}

> 第二步：寻找lowcost中的最小值所在顶点t

int temp = INF;
    		int t = u0;
    		//寻找距离集合U最近的顶点t 
    		for(j = 1; j <= n; j++)
    		{
    			if(lowcost[j] < temp && !s[j])
    			{
    				temp = lowcost[j];
    				t = j;
    			} 
    		}
    		if(t == u0)//没找到t 
    			break;
    		s[t] = true;

> 第三步：更新数组closet和lowcost

for(j = 1; j <= n; j++)
    		{
    			if((!s[j]) && c[t][j] < lowcost[j])
    			{
    				lowcost[j] = c[t][j];
    				closest[j] = t;
    			}
    		}

> 完整代码：

#include<iostream>
    using namespace std;
    const int INF = 0x3fffffff;
    const int N = 100;
    bool s[N];
    int closest[N];
    int lowcost[N];
    void Prim(int n, int u0, int c[N][N])
    {
    	//顶点个数n，开始顶点u0，带权邻接矩阵c[n][n]
    	//如果s[i] = true,说明顶点i已加入最小生成树的顶点集合U；否则顶点i属于集合V-U
    	//将最后的相关最小权值传递到数组lowcost
    	s[u0] = true;//初始时，集合中只有U一个元素，即顶点u0；
    	int i;
    	int j;
    	
    	//初始化 
    	for(i = 1; i <= n; ++i)
    	{
    		if(i != u0)
    		{
    			lowcost[i] = c[u0][i];
    			closest[i] = u0;
    			s[i] = false;
    		}
    		else
    			lowcost[i] = 0;
    	} 
    	
    	//寻找距离集合U最近的顶点t，并更新lowcost和closest（先找最小值，再更新两个数组） 
    	for(i = 0; i <= n; i++)
    	{
    		int temp = INF;
    		int t = u0;
    		//寻找距离集合U最近的顶点t 
    		for(j = 1; j <= n; j++)
    		{
    			if(lowcost[j] < temp && !s[j])
    			{
    				temp = lowcost[j];
    				t = j;
    			} 
    		}
    		if(t == u0)//没找到t 
    			break;
    		s[t] = true;
    		
    		//更新lowcost和closest
    		for(j = 1; j <= n; j++)
    		{
    			if((!s[j]) && c[t][j] < lowcost[j])
    			{
    				lowcost[j] = c[t][j];
    				closest[j] = t;
    			}
    		} 
    	} 
    }
    
    int main()
    {
    	int n, c[N][N], m, u, v, w;
    	int u0;
    	cout << "输入结点数n和边数m: " << endl;
    	cin >> n >> m;
    	int sumcost = 0;
    	
    	for(int i = 1; i <= n; ++i)
    	{
    		for(int j = 1; j <= n; ++j)
    		{
    			if(i == j) c[i][j] = 0;
    			else c[i][j] = INF;
    		}
    	}
    	
    	cout << "输入结点数u、v和边值w: " << endl;
    	for(int i = 1; i <= m; ++ i)
    	{
    		cin >> u >> v >> w;
    		c[u][v] = c[v][u] = w; 
    	}
    	
    	cout << "输入任一结点u0： " << endl;
    	cin >> u0;
    	
    	//计算最后的lowcost的总和，即为最后要求的最小费用之和
    	Prim(n,u0,c);
    	
    	cout << "数组lowcost的内容为： " << endl;
    	for(int i = 1; i <= n; ++i)
    		cout << lowcost[i] << " ";
    	cout << endl;
    	
    	for(int i = 0; i <= n; ++i)
    	{
    		sumcost += lowcost[i]; 
    	} 
    	cout << "最小费用是：" << sumcost << endl;
    	return 0;
    }

![70 6][]

[70]: /images/20220504/ee16aadc45894bdeac868d97e7bfc644.png
[70 1]: /images/20220504/f1fcef54ab22423baf0c2fe6622916fc.png
[70 2]: /images/20220504/dc9319b4f1534b18918dc799f92175e2.png
[70 3]: /images/20220504/8e6a0ba899e74f3d84f87c2f127790c8.png
[70 4]: /images/20220504/16004a0f8ea54fc7bfb18d6c0fc34b37.png
[70 5]: /images/20220504/611499f55dc34866a549e1f8d09616af.png
[70 6]: /images/20220504/434b539caedf403c8fd535e4e8d88080.png