#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 30000    //定义一个权值的最大值
#define MAX_VERTEX_NUM 20 //图的最大顶点数
typedef struct
{
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
	int vexnum,arcnum;                //图的当前顶点和边数
} Graph;
typedef struct
{
	int adjvex;  //某顶点与已构造好的部分生成树的顶点之间权值最小的顶点
	int lowcost; //某顶点与已构造好的部分生成树的顶点之间的最小权值
} ClosEdge[MAX_VERTEX_NUM]; //用普里姆算法求最小生成树时的辅助数组
void CreateGraph ( Graph & ); //生成图的邻接矩阵
void MiniSpanTree_PRIM ( Graph,int ); //用普里姆算法求最小生成树
int  minimum ( ClosEdge,int ); //在普里姆算法中求下一个结点
void main()
{
	Graph G;  //采用邻接矩阵结构的图
	char j='y';
	int u;
	textbackground ( 3 );  //设定屏幕颜色
	textcolor ( 15 );
	clrscr();
//------------------程序解说----------------------------
	printf ( "本程序将演示构造图的最小代价生成树。\n" );
	printf ( "首先输入图的顶点数和弧数.\n格式：顶点数，弧数；例如:4,4\n" );
	printf ( "接着输入各条弧(弧尾,弧头)和弧的权值。\n" );
	printf ( "格式:弧尾，弧头，权值；例如\n1,2,1\n1,3,2\n2,4,3\n3,4,4\n" );
	printf ( "程序将会构造该图的最小代价生成树。\n" );
	printf ( "并显示该最小生成树。\n1,2\n1,3\n2,4\n" );
//------------------------------------------------------
	while ( j!='N'&&j!='n' )
	{
		printf ( "请输入图的顶点和弧数:" );
		scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //输入图的顶点数和边数
		CreateGraph ( G );    //生成邻接矩阵结构的图
		printf ( "从哪一顶点开始:" );
		scanf ( "%d",&u );  //输入普里姆算法中的起始顶点
		MiniSpanTree_PRIM ( G,u ); //普里姆算法求最小生成树
		printf ( "最小代价生成树构造完毕，继续进行吗?(Y/N)" );
		scanf ( " %c",&j );
	}
}

void CreateGraph ( Graph &G )
{//构造邻接矩阵结构的图G
	int i,j;
	int start,end,weight;
	for ( i=1; i<=G.vexnum; i++ )
		for ( j=1; j<=G.vexnum; j++ )
			G.arcs[i][j]=INFINITY; //初始化邻接矩阵
	printf ( "输入弧和其权值，格式：弧尾，弧头，权值\n" );
	for ( i=1; i<=G.arcnum; i++ )
	{
		scanf ( "%d,%d,%d",&start,&end,&weight ); //输入边的起点和终点及权值
		G.arcs[start][end]=weight;
		G.arcs[end][start]=weight;
	}
}
void MiniSpanTree_PRIM ( Graph G,int u )
{//从第u个顶点出发构造图G的最小生成树
	ClosEdge closedge;
	int i,j,k;
	printf ( "最小代价生成树:\n" );
	for ( j=1; j<=G.vexnum; j++ ) //辅助数组初始化
		if ( j!=u )
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[u][j];
		}
	closedge[u].lowcost=0; //初始，U={u}
	for ( i=1; i<G.vexnum; i++ ) //选择其余的G.vexnum-1个顶点
	{
		k=minimum ( closedge,G.vexnum ); //求出生成树的下一个顶点
		printf ( "%d,%d\n",closedge[k].adjvex,k ); //输出生成树的边
		closedge[k].lowcost=0;   //第k顶点并入U集
		for ( j=1; j<=G.vexnum; j++ ) //新顶点并入U后，重新选择最小边
			if ( G.arcs[k][j]<closedge[j].lowcost )
			{
				closedge[j].adjvex=k;
				closedge[j].lowcost=G.arcs[k][j];
			}
	}
}
int minimum ( ClosEdge cl,int vnum )
{//在辅助数组cl[vnum]中选择权值最小的顶点，并返回其位置
	int i;
	int w,p;
	w=INFINITY;
	for ( i=1; i<=vnum; i++ )
		if ( cl[i].lowcost!=0&&cl[i].lowcost<w )
			{w=cl[i].lowcost; p=i;}
	return p;
}