haio.cpp

用C写的一个简单的最小生成树算法

#include<iostream>
#include <fstream>//文件读写的头文件
#include <iomanip>//setw的头文件
#include<algorithm>//sort的头文件
using namespace std;
#define NoEdge 10000//两个节点不连通
#define M 15//最大城市数目
typedef struct//城市节点的信息
{
	int x;//边的一个顶点				   
	int y;//边的另一个顶点
	int w;//边的权值 
}node;
node e[M];//定义有关城市信息的数组


int cmp(node a,node b)//按权小到大快排
{
	return a.w< b.w;
}

void Prim()
{
	int c[7][7];//城市的邻接矩阵
	int lowcost[7];//与节点i连通的最小边
	int closest[7];//与节点i连通的最小顶点
	bool s[7];//是否连通的标志
	int min;
	int j;

	s[1] = true;//城市1连通
	cout<<"读入6个城市的邻接矩阵."<<endl;
	cout<<"请等待……"<<endl;
	cout<<endl;
	ifstream ptr("tree.txt");//打开文件
	for(int a = 1;a <= 6;a ++)
		for(int b = 1;b <= 6;b ++)
			ptr >> c[a][b];//读入邻接矩阵
		ptr.close();//关闭文件
	cout<<"6个城市的邻接矩阵(若两点没有连通就输入10000，规定点到自身的距离为0。):"<<endl;
	for(a = 1;a <= 6;a ++)//数组的0行0列没有使用
	{
		for(int b = 1;b <= 6;b ++)//输出邻接拒阵
			cout<<setw(6)<< c[a][b];
		cout<<endl;
	}
	for (int i = 2;i <= 6;i ++)//初始化
	{
		lowcost[i] = c[1][i];
		closest[i] = 1;
		s[i] = false;//将节点分为连通和非连通的两个集合
	}
	cout<<"最小生成树为:"<<endl;	
	for (i = 1;i < 6;i++)
	{
		min = NoEdge;//每次循环之初进行初始化
		j = 1;
		for (int k = 2;k <= 6;k ++)//通过循环找出最小边
		{
			if (lowcost[k] < min && (!s[k]))//有边且另一节点没有连通
			{
				min = lowcost[k];
				j = k;
			}	
		}
		cout<<j<<' '<<closest[j]<<endl;//输出节点j
		s[j] = true;//节点j加入连通集合
		for(k = 2; k <= 6;k ++)//
		{
			if (c[j][k] < lowcost[k] && (!s[k]))//找出与j最近的边且没有该边的另一顶点没有连通
			{
				lowcost[k] = c[j][k];//对辅助数组进行修改
				closest[k] = j;//对辅助数组进行修改
			}
		}
	}
	cout<<endl;
}
void Kruskal()
{
	int n;//城市个数（从0开始编号）
	int m;//城市之间边的条数
    int i,j,m1,m2,sn1,sn2,k;
    int vest[M];//辅助数组

	cout<<"读入城市个数和城市个数……"<<endl;
	cout<<"请等待……"<<endl;
	ifstream ptr("node.txt");//打开文件
    ptr>>n;//读入城市个数
	ptr>>m;//读入边的条数
	cout<<"城市个数为："<<n<<endl;//显示提示信息
	cout<<"城市个数:"<<m<<endl;
	cout<<"正读入城市节点的信息……"<<endl;
	for(i = 0;i < m;i++)//读入城市节点的信息
	{
		ptr>>e[i].x;//顶点
		ptr>>e[i].y;//顶点
		ptr>>e[i].w;//权值
	}
	cout<<"城市信息读入完毕."<<endl;
	ptr.close();//关闭文件
    sort(e,e+m,cmp);//将节点按边的值从小到大排序
	for(i = 0;i < n;i ++) 
	   vest[i]=i; //初始化辅助数组
    k=1;
    j=0;
	cout<<"最小生成树为:"<<endl;
    while(k < n) //n-1条边
    {//主要思想贪心算法
		m1 = e[j].x;//临时变量
		m2 = e[j].y;//临时变量
        sn1 = vest[m1];//临时变量
		sn2 = vest[m2];//临时变量
        if(sn1 != sn2)//两个顶点不相等
        {
			cout<<"("<<m1<<","<<m2<<"):"<<e[j].w<<endl;//输出最小生成树
            k++;   //生成数+1
            for(i=0;i < n;i ++)
				if(vest[i] == sn2) //并入mst集合;
					vest[i] = sn1; //两个顶点相等，古避免了产生回路                   
        }                          
        j ++;//改变循环变量，对下一条边搜索
    }
}
int main()//主函数
{
	int choice;

	do//菜单显示.
	{
		cout<<endl;
		cout<<"////////////////////////////////"<<endl;
		cout<<"//                            //"<<endl;
		cout<<"//     1     Prim算法         //"<<endl;
		cout<<"//     2     Kruskal算法      //"<<endl;
		cout<<"//                            //"<<endl;
		cout<<"////////////////////////////////"<<endl;
		cout<<endl;
		cout<<"输入你的选择：（输入非1和2结束）"<<endl;
		cin>>choice;//输入选择.
		switch(choice)//两种主要的算法
		{
			case 1:
				Prim();
				break;
			case 2:
				Kruskal();
				break;
			default:
				cout<<"结束!"<<endl;
				break;	
		}			
	}while(choice == 1 || choice == 2);//输入非1和2结束选择.

	return 0;
}