prim贪心求最小生成树

算法描述

• 先随意选一个点作为起点
• 将各个与起点之间连通的点之中权值最小的那个与点加入到最小生成树中
• 继续遍历与最小生成树中的点权值最小的点（未加入最小生成树的点），将它加入最小生成树中
• 重复第三个步骤直到所有的点加入到最小生成树中

与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
复制代码