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算法的初步了解》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

现代编译原理

现代编译原理

(美)安佩尔 / 赵克佳、黄春、沈志宇 / 人民邮电出版社 / 2006-4 / 45.00元

《现代编译原理:C语言描述》全面讲述了现代编译器的结构、编译算法和实现方法,是Andrew w.Apple的“虎书”——Modern Compiler Implementation——“红、蓝、绿”三序列之一。这三本书的内容基本相同。但是使用不同的语言来实现书中给出的一个编译器。本书使用的是更适合广大读者的c语言,而另外两本书分别采用ML语言和Java语言。本书的另一个特点是增加了一些其他编译原理......一起来看看 《现代编译原理》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具