prim算法的初步了解

栏目: 编程工具 · 发布时间: 5年前

内容简介:不用判断加入的点是否会形成连通图
  • 先随意选一个点作为起点
  • 将各个与起点之间连通的点之中权值最小的那个与点加入到最小生成树中
  • 继续遍历与最小生成树中的点权值最小的点(未加入最小生成树的点),将它加入最小生成树中
  • 重复第三个步骤直到所有的点加入到最小生成树中

与kruskal相比的优点

不用判断加入的点是否会形成连通图

算法步骤

  1. 将各个点之间的距离以无向图的形式存在邻接矩阵中。
  2. 用一个一维数组存储起始点到各个点的距离。
  3. 用一个标记数组存储各个点加入最小生成树的状态。
  4. 用一个数组记录当前节点是哪个节点连过来的。
  5. 所谓贪心,就是每次都找到权值最小的那条边(u,v)的v加入到最小生成树中,加进去之后对标记数组进行修改,表示该点已经加入到最小生成树中。对v中的距离数组进行更新,这里的更新不是把原数组中的所有数据都替换到新加入的点到所有的点的距离,而是与原先的点到同一个点(未加入)进行比较。倘若比原来的小则更新数组数据,同时对4中的来源数组进行更新,用来记录最小生成树,大于等于就跳过。循环n次(节点个数)后得到结果。

代码

#include<stdio.h>
#define N 6
#define MAX 100000
int a[N][N],result[N][N];

int main()
{
	int flag[100] = { 0 };
	int neighbor[100],distance[100];
	int u, v, l;
	//对数据进行初始化
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			a[i][j] = MAX;
	}
	scanf("%d%d%d", &u, &v, &l);
	while (l != -1)
	{
		a[u][v] = l;
		a[v][u] = l;
		scanf("%d%d%d", &u, &v, &l);
	}
	for (int i = 0; i < N; i++)
	{
		neighbor[i] = 0;
		distance[i] = a[0][i];
	}
	flag[0] = 1;//以第0个点为起点
	for (int i = 1; i < N; i++)
	{
		int min = MAX;
		for (int j = 0; j < N; j++)
		{
			if (!flag[j] && min>distance[j])
			{
				min = distance[j];
				v = j;
			}
		}//找到距离最短那条边,并把v加进最小生成树
		if (min < MAX)
		{
			flag[v] = 1;
			result[neighbor[v]][v] = distance[v];
			result[v][neighbor[v]] = distance[v];
			for (int j = 0; j < N; j++)
			{
				//更新distance数组,将距离小的加进去
				if (!flag[j] && a[v][j] < distance[j])
				{
					distance[j] = a[v][j];
					neighbor[j] = v;//更新来源
				}

			}
		}
		else break;
	}
	//将结果输出
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			printf("%d ",result[i][j]);
		putchar(10);//换行
	}
	return 0;
}
复制代码

测试数据

0 1 5
0 2 6
0 3 4
1 2 1
1 3 2
2 3 2
2 4 5
2 5 3
3 5 4
4 5 4
-1 -1 -1
复制代码

以上所述就是小编给大家介绍的《prim算法的初步了解》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法

算法

Robert Sedgewick、Kevin Wayne / 人民邮电出版社 / 2012-3 / 99.00元

《算法(英文版•第4版)》作为算法领域经典的参考书,全面介绍了关于算法和数据结构的必备知识,并特别针对排序、搜索、图处理和字符串处理进行了论述。第4版具体给出了每位程序员应知应会的50个算法,提供了实际代码,而且这些Java代码实现采用了模块化的编程风格,读者可以方便地加以改造。本书配套网站提供了本书内容的摘要及更多的代码实现、测试数据、练习、教学课件等资源。 《算法(英文版•第4版)》适合......一起来看看 《算法》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具