(13)最小生成树.cpp

这是一个关于数据结构中最小生成树的源代码

#include<iostream.h>
#include<conio.h>
#include<stdio.h>

int NodeCount;
char Node[20];
char Graph[20][20];
char Queue[20];
char Checked[20];

char Locate(char Char)
{
	char Temp;
	for(Temp=0;Temp<NodeCount;Temp++)
		if(Node[Temp]==Char)
			break;
	return Temp;
}

void main()
{
	char Temp1,Temp2;
	int Temp3;
	char min,mintemp,mintemp1;
	//clrscr();
	for(Temp2=0;Temp2<20;Temp2++)
		for(Temp1=0;Temp1<20;Temp1++)
			Graph[Temp2][Temp1]=0;
	for(Temp1=0;Temp1<20;Temp1++)
	{
			Queue[Temp1]=0;
			Checked[Temp1]=0;
	}
	cout<<"Input the node count:";
	cin>>NodeCount;
	cout<<"Input the node:";
	for(Temp1=0;Temp1<NodeCount;Temp1++)
		  cin>>Node[Temp1];
	cout<<"Input the link"<<endl;
	Temp1=0;
	while(1)
	{
		cout<<"Input the first node:";
		cin>>Temp1;
		cout<<"Input the second node:";
		cin>>Temp2;
		cout<<"Input the weight:";
		cin>>Temp3;
		if(Temp1=='$')
			break;
		Temp1=Locate(Temp1);
		Temp2=Locate(Temp2);
		Graph[Temp2][Temp1]=Temp3;
		Graph[Temp1][Temp2]=Temp3;
	}
	for(Temp2=0;Temp2<NodeCount;Temp2++)
	{
		for(Temp1=0;Temp1<NodeCount;Temp1++)
			cout<<(int)Graph[Temp2][Temp1]<<" ";
		cout<<endl;
	}
	Queue[0]=0;
	Checked[0]=1;
	for(Temp1=1;Temp1<NodeCount;Temp1++)
	{
		min=100;
		for(Temp2=0;Temp2<Temp1;Temp2++)
			for(Temp3=0;Temp3<NodeCount;Temp3++)
				if((!Checked[Temp3])&&(Graph[Queue[Temp2]][Temp3]>0)&&(Graph[Queue[Temp2]][Temp3]<min))
				{
					min=Graph[Queue[Temp2]][Temp3];
					mintemp=Temp3;
					mintemp1=Queue[Temp2];

				}
		cout<<Node[mintemp1]<<"->"<<Node[mintemp]<<endl;
		Checked[mintemp]=1;
		Queue[Temp1]=mintemp;
	}
}