kruskal.cpp

This kruskal Minimum Spanning Tree!It s good for user in Coding Programming.

// kruskal.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <iostream>

#define  MaxEdge    100				//最大的边的数量
#define  MaxPoint   200				//最大的点的数量

//定义边的数据类型
typedef struct  
{
	int fromvex,endvex;				//边的起点和终点
	float length;					//边的权值(实际中则是城市间的通信量)
	int  sign;						//该边是否已选择过的标志信息
}edge;

edge T[MaxEdge];					//定义最大值为100的边的数组
int  G[MaxPoint];					//判断该边的两个顶点是否在同一分量上的数组，n为顶点数

void DisplayScreen();				//显示题目的输入和输出信息
void Kruskal(int n,int e);			//用kruskal算法求最小生成树，输入为顶点数n，边数e

int main(int argc, char* argv[])
{
	//变量初始化
	int n=0;
	int e=0;
	int chChoice=1;

	while(chChoice) 
	{
		system("cls");											//DOS清屏
		DisplayScreen();										//显示题目的输入和输出信息

		//输入顶点数n和边数e
		printf("Please input the number of points:");
		scanf("%d",&n);
		printf("Please input the number of edges:");
		scanf("%d",&e);

		//用kruskal算法求最小生成树，输入为顶点数n，边数e
		Kruskal(n,e);

		printf("Do you want to continue?Please input 0/1(1-Yes,0-No):");
		scanf("%d",&chChoice);									//是否继续
	} 
	
	return 0;
}


//*********************显示题目的输入和输出信息*******************************
void DisplayScreen()
{
	printf("************************************************************\n");
	printf("***                                                      ***\n");
	printf("***                最小生成树问题                        ***\n");
	printf("***问题描述: 在n个城市之间建设通信网络，如何以最低的经济 ***\n");
	printf("***          代价建设这个通信网。                        ***\n");
	printf("***输入数据: 点(即城市)的数量n，边(城市间的有效通信链路, ***\n");
	printf("***          即通信量小于无穷)的数量e，城市间的通信量如：***\n");
	printf("***          (0,1)=12,表示：从城市0到城市1的通信量为12   ***\n");
	printf("***输出数据: 按Kruskal算法构造顺序输出生成树中各条链以及 ***\n");
	printf("***          他们的对应的通信量值。                      ***\n");
	printf("***                                                      ***\n");
	printf("************************************************************\n");
	printf("\n");
}


//**************用kruskal算法求最小生成树，输入为顶点数n，边数e***************
void Kruskal(int n,int e)
{
	int i,j,k,m,p,tempflag;
	float min;

	for (i=0;i<=n-1;i++)							//数组G置初值
	{
		G[i]=i;
	}

	for (i=0;i<=e-1;i++)							//输入边信息，注意：顶点的编号从0开始编号
	{
		printf("Please input the %d edge(such as:0 1 12):\n",i);
		scanf("%d %d %f",&T[i].fromvex,&T[i].endvex,&T[i].length); //输入时注意两个输入之间需要空格
		T[i].sign=0;
	}

	printf("Display all edges:\n");					//打印出输入的所以边信息
	for (i=0;i<=e-1;i++)
	{
		printf("(%d,%d) =%f\n",T[i].fromvex,T[i].endvex,T[i].length);
	}
	printf("\nThe Minimum Spanning Tree By Minimum Spanning Tree:\n");
	
	j=0;

	while (j<n-1)
	{
		min=10000;									//min=10000 当作无穷大
		for (i=0;i<=e-1;i++)						//寻找最短边
		{
			if (T[i].sign==0)
			{
				if (T[i].length<min)
				{
					min=T[i].length;
					k=T[i].fromvex;
					m=T[i].endvex;
					p=i;							//记录最小边的编号	
				}
			}
		}
	                                 
		if (G[k]==G[m])								//在同一分量上舍去
		{
			T[p].sign=2;
		}
		else
		{
			j++;
			tempflag=G[m];							//将顶点m的信息保存作为判断依据，因为下面可能会被改变
			for (i=0;i<n;i++)
			{				
				if (G[i]==tempflag)					//将最短边的两个顶点并入同一分量
				{
					G[i]=G[k];						
				}
			}
			T[p].sign=1;							//编号为p的边已被选择了

			//按Kruskal算法构造顺序输出生成树中各条链以及他们的对应的通信量值。
			printf("(%d,%d)=%f \n",T[p].fromvex,T[p].endvex,T[p].length);		
		}

	}
}