zui_xiao_sheng_cheng_shu.txt

最小生成树 一．问题描述 构造一无向连通网

#include <iostream>
#include <iomanip>
#include <string>                       
using namespace std;
const int MaxSize=15;                     //图中最多顶点个数
const int MaxValue=200;
int lowcost[MaxSize],adjvex[MaxSize];
struct RCW 
{ int row,col;//行号，列号
  int weight; //权值
};
class MGraph
{
public:
    MGraph(RCW a[],int n,int e);          //构造函数，初始化具有n个顶点的图
	~MGraph(){}
	void BFSprint(); 
friend void Dijkstra(MGraph G,int v);  //最短路径算法，其中v为源点
private:
    char vertex[MaxSize];                 //存放图中顶点的数组
    int arc[MaxSize][MaxSize];             //存放图中边的数组
    int vertexNum,arcNum;                  //图的顶点数和边数
	int visited[MaxSize];
 };
MGraph::MGraph(RCW a[], int n, int e) //构造函数，初始化具有n个顶点的图
{
 vertexNum=n;                 //顶点数
 arcNum=e;                    //边数
 int i,j,k;
 for(i=0;i<vertexNum;i++)
	 vertex[i]=char(65+i);
 for (i=0; i<vertexNum; i++)    //初始化邻接矩阵
	 for (j=0; j<vertexNum; j++)
		 if(i==j)arc[i][j]=0;
		 else arc[i][j]=MaxValue;
 for(k=0;k<arcNum;k++)
	 arc[a[k].row][a[k].col]=a[k].weight;
}
void MGraph::BFSprint()//创建图的邻接矩阵
{
	int i,j;
	for(i=0;i<vertexNum;i++){
		for(j=0;j<vertexNum;j++)
			if(arc[i][j]==MaxValue)cout<<setw(4)<<"∞";
			else cout<<setw(4)<<arc[i][j];
		cout<<endl;
	}
}
void Dijkstra(MGraph g,int v) //单源点最短路径Dijkstra算法
{ 	int *dist,num,k,N=g.vertexNum+1,loc=0;;
	char **path,*temp,*s=new char[N];
	dist=new int[N-1];
	path=new char*[N-1];
    temp=new char[N];
	for(int i=0;i<8;i++)
path[i]=new char[N];
	for ( i=0;i<g.vertexNum;i++)
	{   dist[i]=g.arc[v][i];
		if(dist[i]!=MaxValue)
		{
			path[i][0]=g.vertex[v];
			path[i][1]=g.vertex[i];
			path[i][2]='\0'; 
		}
		else path[i][0]='\0';
	}
	s[0]=g.vertex[v];
	dist[v]=0;
	num=1;
	while(num<g.vertexNum)
	{
		k=0;
		for (int i=0;i<g.vertexNum;i++)
			if(((dist[i]<dist[k])&&dist[i]!=0)||dist[k]==0)k=i;
			if(path[k][0]!='\0')
 cout<<"Path:"<<setw(N)<<path[k]<<"  *shortpathvalue*:"<<dist[k]<<endl;
		s[num++]=g.vertex[k];
		s[num+1]='\0';
	    for(i=0;i<g.vertexNum;i++)
		if(dist[i]>dist[k]+g.arc[k][i])
		{
					dist[i]=dist[k]+g.arc[k][i];
					strcpy(temp,path[k]);
					while(path[k][loc]!='\0')loc++;
					temp[loc+1]='\0';
                    temp[loc]=g.vertex[i];
					strcpy(path[i],temp);
				}
            dist[k]=0;     
	}
}
void main(void)
{
	int v,e,no;
	char node;
	RCW * vname;
	cout<<"输入图的点数(<15)："<<endl;
	cin>>v;
	cout<<"输入点数为"<<v<<"的图边数"<<endl;
	cin>>e;
	vname=new RCW[e];//初始化RCW[]图的初始化数据
	cout<<"依次输入无向图的每条边的起点和终点序号及权值!"<<endl;
	for (int i=0;i<e;i++)
  cin>>vname[i].row>>vname[i].col>>vname[i].weight; //调用Graph程序构造函数
	MGraph g(vname,v,e);       
	cout<<"创建后的邻接矩阵"<<endl;
	g.BFSprint();
	while(1){
	cout<<"************Dijkstra算法求最短路径***********"<<endl;
	cout<<"输入始点,范围(";
	for(i=0;i<v;i++)cout<<char(65+i)<<" ";
	cout<<")"<<endl;
	cin>>node;
	no=int(node-65);
	if(no>=v){cout<<"结点越界!!!!"<<endl;exit(1);}
	cout<<"输出源点"<<node<<"到其他结点的最短路径"<<endl;
    Dijkstra(g,no);
	cout<<endl;
	}}