galaxy

用户名：yppp

访问量：9146

签　名：

你只需要做的便是厚积薄发

等　　级
排　　名	1609
经　　验	2649
参赛次数	7
文章发表	18
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

酸菜鱼与黄焖鸡

TA的其他文章

数据结构-Dijskra(迪杰斯特拉)最短路径算法-题解（C++代码）
浏览：239

数据结构-最小生成树-题解（C++代码）
浏览：290

P1001-题解（C++代码）
浏览：200

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

A+B for Input-Output Practice (VII) （C++代码）

数据结构-最小生成树-题解（C++代码）

　　作者: galaxy　　　　发表时间：2020-06-01 12:26:54 浏览：290　|　评论：0　

原题链接：数据结构-最小生成树

这题用prim算法解决最小生成树的思想与用dijkstra算法解决最段路径的思想几乎完全相同，可以看看我上一篇关于dijkstra算法的文章，谢谢。

好了，话不多说，代码搞起来。

#include<iostream>
    using namespace std;
    const int N = 50;
    const int INF = 100000000;
    int Graph[N][N];
    int d[N];
    bool visit[N];
    int n;
    //普利姆算法适合求解提供源点的算法
	//将最小生成树的所有点看作一个集合，里面的每一个点都属于这个集合
	//生成最小生成树的过程就是把点一个一个加入集合的过程。
    int prim(int s)
    {
    	d[s] = 0;//更新源点的距离
    	int ans = 0;//最小生成树的权值之和
    	for (int i = 0; i < n; i++)
    	{
    		int min = INF;
    		int index = -1;
    		for (int j = 0; j < n; j++)
    		{
    			if (visit[j] == false && d[j] < min)
    			{
    				min = d[j];
    				index = j;
    			}
    		}
    		if (index == -1)
    		{
    			return INF;//此图不连通
    		}
    		visit[index] = true;
    		ans += d[index];
    		for (int k=0;k<n;k++)
    		{
    			if (visit[k] == false &&d[k]>Graph[index][k])
    			{
    				d[k] = Graph[index][k];//这就是不同点，更新点到集合的最小距离即可
    			}
    		}
    	}
    	return ans;
    }
    int main()
    {
    	cin >> n;
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j < n; j++)
    		{
    			cin >> Graph[i][j];
    			if (Graph[i][j] == 0)
    			{
    				Graph[i][j] = INF;
    			}
    		}
    	}
		//如果原来的图里面任何两条边长都不相同，那么最小生成树是唯一的，
		//此时不管用什么方法算出来的都是一样的。但是如果图里有相等的边，
		//那么最小生成树可能不唯一，这样就无法保证不同的方法得到同一棵树
		//（即使是同一个算法，只内要图的编号方式改变也容可能得到不同的最小生成树）
		//所以在这里，我们运用循环 把每一个点当成源点，计算最小生成树的权值之和
		int  ans;
    	int min = INF;
    	for (int i = 0; i < n; i++)
    	{prim算法适合给你源点，这里没有需要我们自己来
		每一次都要把visit和d数组更新
    		for (int i = 0; i < n; i++)
    		{
    			visit[i] = false;
    			d[i] = INF;
    		}
    		ans = prim(i);
			取最小值输出
     		if (ans < min)
    		{
    			min = ans;
    		}
    	}
    	cout << min << endl;
    	return 0;
    }

0.0分

2 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

galaxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

人见人爱A+B （C语言代码）

数据结构-最小生成树-题解（C++代码）

评论区

精彩推荐

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

简单的a+b （C++语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

蛇行矩阵（C语言代码）

求组合数（C语言代码）

三角形（C语言代码）

求圆的面积（C语言代码）

剪刀石头布（C语言代码）

简单的a+b （C语言代码）

galaxy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

人见人爱A+B （C语言代码）

数据结构-最小生成树-题解（C++代码）

评论区

精彩推荐

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

简单的a+b （C++语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

蛇行矩阵 （C语言代码）

求组合数 （C语言代码）

三角形 （C语言代码）

求圆的面积 （C语言代码）

剪刀石头布 （C语言代码）

简单的a+b （C语言代码）

　　评论区

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

蛇行矩阵（C语言代码）

求组合数（C语言代码）

三角形（C语言代码）

求圆的面积（C语言代码）

剪刀石头布（C语言代码）