最小生成树算法

  1. 云栖社区>
  2. 博客列表>
  3. 正文

最小生成树算法

hybcoder 2013-05-31 19:33:00 浏览346 评论0

摘要: #include <stdio.h> #include <string.h> #define INFINITY 1000000 // 无穷大 #define MAX_VERTEX_COUNT 6 // 图最多顶点数 // 图的邻接矩阵 typedef int Graph[MAX_VER...

#include <stdio.h>
#include <string.h>

#define INFINITY 1000000    // 无穷大
#define MAX_VERTEX_COUNT 6 // 图最多顶点数

// 图的邻接矩阵
typedef int Graph[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];

/************************************************************************/
/* 功能:用Prim算法实现构造最小生成树
/* 参数:g--图 
/*       vertexCount -- 图的顶点数
/*       father -- 记录顶点的双亲
/************************************************************************/
void Prim(Graph g, int vertexCount, int father[])
{
	int i, j, k;
    int lowCost[MAX_VERTEX_COUNT]; // 记录从U到V-U具有最小代价的边
	int closeSet[MAX_VERTEX_COUNT];// 记录了该边依附的在U中的顶点,v属于V-U 
	int used[MAX_VERTEX_COUNT];    // 记录顶点是否已经被选中放入到U集合中
	int min;

	// 这里初始选中顶点为1号顶点,这是可以修改的,本程序以1号顶点为默认
	for (i = 0; i < vertexCount; i++)
	{
		// 最短距离初始化为其他节点到1号节点的距离
		lowCost[i] = g[0][i];

		// 标记所有节点的依附点皆为默认的1号节点
		closeSet[i] = 0;

		// 所有顶点均未被选中到U集合中
		used[i] = 0; 

		// U集合中还没有顶点,所有值设为-1,表示无双亲
		father[i] = -1;
	}

	used[0] = 1; // 1号顶点选中,并加入到集合U中
	// 依次选取剩余顶点加入到集合中
	for (i = 1; i < vertexCount; i++)
	{
		j = 0;
		min = INFINITY;

		// 找满足条件的最小权值边的顶点k及其编号
		for (k = 1; k < vertexCount; k++)
		{
			// 边权值较小且不在生成树中
			if (!used[k] && lowCost[k] < min)
			{
				min = lowCost[k]; // 选中顶点
				j = k;
			}
		}
		father[j] = closeSet[j]; // 记录j号顶点的双亲
		used[j] = 1; // 将j号顶点选入到生成树中

		// 打印边即打印该边连接的两个顶点(权值最小)
		printf("%d %d\n",j + 1,closeSet[j] + 1);

		for (k = 1; k < vertexCount; k++)
		{
			// 继续找边权值更小的顶点
			if (!used[k] && g[j][k] < lowCost[k])
			{
				lowCost[k] = g[j][k]; // 更新最小权值
				closeSet[k] = j; // 记录新的依附点
			}
		}
	}

}


int main()
{
	int i, j, weight;
    Graph g;
    int father[MAX_VERTEX_COUNT];
	int vertexCount;

	for (i = 0; i < MAX_VERTEX_COUNT; i++)
	{
		for (j = 0; j < MAX_VERTEX_COUNT; j++)
		{
			g[i][j] = INFINITY;
		}
	}

	// 构造图
	while (scanf("%d%d%d", &i, &j, &weight) != EOF)
	{
		// 无向图是对称的
		g[i - 1][j - 1] = weight;
		g[j - 1][i - 1] = weight;
	}

	Prim(g, 6, father);

	return 0;
}

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

hybcoder
文章522篇 | 关注17
关注
提供基于开源Elasticsearch及商业版X-pack插件,致力于数据分析、数据搜索等场... 查看详情
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
一款阿里巴巴自主研发的高性能、分布式的关系型数据库,支持完整的ACID特性。它高度兼容MyS... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航