prim.cpp

来自「数据结构学习过程中的实验 PRIM算法」· C++ 代码 · 共 128 行

#include <iostream>
#include <stdio.h>
using namespace std;

#define NO 100	//设最大顶点数为100
#define MAX 32767	//设32767为最大整数

struct mgraph
{
	int adjmatrix[NO+1][NO+1];//定义邻接距阵
};
struct mgraph MH;
int n, e, Q;//定义顶点数和边或弧数

void creatmgraph(int n, int e)//创建图的邻接距阵
{
	int i,j,k,t;//i为行数 ；j为列数；k为两点间距离；
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		MH.adjmatrix[i][j]=MAX;//点与点的距离信息
	}


  if(Q==1)
	{
		cout<<"请输入无向图相关邻接距阵的信息(点、距离,输3次)："<<endl;
		for(t=1;t<=e;t++)	
		{	
			cin>>i>>j>>k;	
			cout<<"i="<<i<<"	"<<"j="<<j<<endl;	
			cout<<i<<"到"<<j<<"距离为："<<k<<endl;		
			MH.adjmatrix[i][j]=MH.adjmatrix[j][i]=k;//点与点的距离信息		
			if(t!=e)
				cout<<"请继续输入"<<endl;
		}
	}

	else   if(Q==2)
	{
		cout<<"请输入有向相关邻接距阵的信息(点、距离,输3次)："<<endl;
		for(t=1;t<=e;t++)	
		{	
			cin>>i>>j>>k;
			cout<<"i="<<i<<"	"<<"j="<<j<<endl;	
			cout<<i<<"到"<<j<<"距离为："<<k<<endl;		
			MH.adjmatrix[i][j]=k;//点与点的距离信息		
			if(t!=e)
				cout<<"请继续输入"<<endl;
		}
	}

}

void printMH(struct mgraph MH)
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			cout<<MH.adjmatrix[i][j]<<"	";
		cout<<endl<<endl;
	}
}

void prim(int x)
{
	int i,j,k;
	int mintotree[NO+1];//存放顶点i的到树中顶点最近距离
	int closet[NO+1];//存放顶点i的到树中最近距离的顶点序号
	int min = 32767;

	for(i=1;i<=n;i++)//初始化
	{
		mintotree[i] = MH.adjmatrix[i][x];
		closet[i] = x ;//邻接到X
	}

	for( i=2; i<=n; i++)
	{
		k=0;
		min=32767;
		for(j=1;j<=n;j++)
		{
			if(mintotree[j]!=0 && mintotree[j]< min)//判断与生成树的最近距离
			{
				k=j;
				min=mintotree[j];
			}
		}

		if(k==0) break; //
		mintotree[k]=0;//标记：距离为0， k进树
		for(j=1;j<=n;j++)
		{
			if(mintotree[j]!=0 && MH.adjmatrix[k][j]<mintotree[j])//判断
			{
				mintotree[j]=MH.adjmatrix[k][j];
				closet[j]=k;
			}
		}

	}
	for(j=1;j<=n;j++)
	{
		if(j!=closet[j])
			cout<<j<<"->"<<closet[j]<<"	"<<MH.adjmatrix[j][closet[j]]<<endl;
	}
}


void main()
{
	cout<<"输入图顶点数和边或弧数："<<endl;
	cin>>n>>e;
	cout<<"无向或有向：1、无向；	2、有向"<<endl;
	cin>>Q;
	creatmgraph(n,e);//创建图的邻接距阵
	printMH(MH);
	cout<<"	PRIM算法求最小生成树"<<endl;
	cout<<"请输入任意一个顶点（1~n），开始"<<endl;
	int x;//定义任选的顶点序号
	cin>>x;
	prim(x);
}