【数据结构】普里姆算法

学习比较痛苦的一个普里姆算法，别废话了！上码如下：

/*
	名称：普里姆算法 
	语言：数据结构C语言版 
	编译环境：VC++ 6.0
	日期：2014-3-25 
*/
#include <stdio.h>
#include <limits.h>
#include <malloc.h>    
#include<cstdlib> 
#include <string.h>  

#define MAX_VERTEX_NUM 20	// 最大顶点个数
#define MAX_NAME 3 // 顶点字符串的最大长度+1 
#define MAX_INFO 20 // 相关信息字符串的最大长度+1 
#define INFINITY INT_MAX	// 用整型最大值代替∞
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];

// 邻接矩阵的数据结构
typedef struct
{
	VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； 
				// 对带权图，则为权值类型 
	InfoType *info; // 该弧相关信息的指针(可无) 
 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 图的数据结构
typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];	// 顶点向量
	AdjMatrix arcs;		// 邻接矩阵
	int vexnum,// 图的当前顶点数
		arcnum;			// 图的当前弧数
} MGraph;

// 记录从顶点集U到V-U的代价最小的边的辅助数组定义
typedef struct
{
	VertexType adjvex;
	VRType lowcost;
}minside[MAX_VERTEX_NUM];


// 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
int LocateVex(MGraph G,VertexType u)
{
	int i;
	for(i = 0; i < G.vexnum; ++i)
		if( strcmp(u,G.vexs[i]) == 0)
			return i;
	return -1;
}

// 算法7.2  P162
// 采用数组(邻接矩阵)表示法,构造无向网G。
int CreateAN(MGraph *G)
{
	int i,j,k,w,IncInfo;
	char s[MAX_INFO],*info;
	VertexType va,vb;
	
	printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分) ");
	scanf("%d%d%d%*c",&(*G).vexnum,&(*G).arcnum,&IncInfo); 
	printf("请输入%d个顶点的值(<%d个字符):n",(*G).vexnum,MAX_NAME);
	for(i=0;i<(*G).vexnum;++i) // 构造顶点向量 
		scanf("%s",(*G).vexs[i]);
	for(i=0;i<(*G).vexnum;++i) // 初始化邻接矩阵 
		for(j=0;j<(*G).vexnum;++j)
		{
			(*G).arcs[i][j].adj=INFINITY; // 网初始化为无穷大 
			(*G).arcs[i][j].info=NULL;
		}
	printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): n",(*G).arcnum);
	for(k=0;k<(*G).arcnum;++k)
	{
		scanf("%s%s%d%*c",va,vb,&w); // %*c吃掉回车符 
		i=LocateVex(*G,va);
		j=LocateVex(*G,vb);
		(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; // 无向 
		if(IncInfo)
		{
			printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
			gets(s);
			w=strlen(s);
			if(w)
			{
				info=(char*)malloc((w+1)*sizeof(char));
				strcpy(info,s);
				(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; // 无向 
			}
		}
	}
	return 1;
}


// 求closedge.lowcost的最小正值
int minimum(minside SZ,MGraph G)
{
	int i=0,min;
	while(!SZ[i].lowcost)
		i++;
	min=SZ[i].lowcost; // 第一个不为0的值 
	k=i;
	for(j=i+1;j<G.vexnum;j++)
		if(SZ[j].lowcost>0)
			if(min>SZ[j].lowcost)
			{
				min=SZ[j].lowcost;
				k=j;
			}
	return k;
}

// 算法7.9 P175 
// 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{
	int i,k;
	minside closedge;
	k=LocateVex(G,u);
	for(j=0;j<G.vexnum;++j) // 辅助数组初始化 
	{
		if(j!=k)
		{
			strcpy(closedge[j].adjvex,u);
			closedge[j].lowcost=G.arcs[k][j].adj;
		}
	}
	closedge[k].lowcost=0; // 初始,U={u} 
	printf("最小代价生成树的各条边为:n");
	for(i=1;i<G.vexnum;++i)
	{ // 选择其余G.vexnum-1个顶点 
		k=minimum(closedge,G); // 求出T的下一个结点：第K顶点 
		printf("(%s-%s)n",closedge[k].adjvex,G.vexs[k]); // 输出生成树的边 
		closedge[k].lowcost=0; // 第K顶点并入U集 
		for(j=0;j<G.vexnum;++j)
			if(G.arcs[k][j].adj<closedge[j].lowcost)
			{
				// 新顶点并入U集后重新选择最小边 
				strcpy(closedge[j].adjvex,G.vexs[k]);
				closedge[j].lowcost=G.arcs[k][j].adj;
			}
	}
}

int main()
{
	MGraph G;
	CreateAN(&G);
	MiniSpanTree_PRIM(G,G.vexs[0]);
	
	system("pause");
	return 0;
}

/*
输出效果：

请输入无向网G的顶点数,否:0):(空格区分) 4 4 0
请输入4个顶点的值(<3个字符):
a
b
c
d
请输入4条边的顶点1 顶点2 权值(以空格作为间隔):
a b 1
a c 2
b d 3
a d 1
最小代价生成树的各条边为:
(a-b)
(a-d)
(a-c)
请按任意键继续. . . 

*/

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!