我的最小生成树.cpp

是一些串操作、赫夫曼树、我的最小生成树的源码希望能帮助大家希望站长能够支持我

 /*在minimum函数中, start = i; 改为 k = i; */
//***************************用普里姆算法求最小生成树************************** 
# include<iostream.h>
# include<stdlib.h>
# include<string.h>
# include<limits.h>

# define OVERFLOW  -2
# define OK   1
# define INFINITY  INT_MAX
# define MAX_VERTEX_NUM   30

typedef int Status;
typedef int VRType;
typedef char VertexType;

typedef struct ArcCell{
	VRType  adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
	VertexType  vexs[MAX_VERTEX_NUM];
	AdjMatrix   arcs;
	int   vexnum,arcnum;
}MGraph;
typedef struct{
	VertexType adjvex;
	VRType  lowcost;
}close;

Status CreateUDN(MGraph &);
int  LocateVex(MGraph &,VertexType);
int  minimum(int);
void MiniSpanTree_PRIM(MGraph &,VertexType);
void Print_Graph(MGraph G);

 close closedge[MAX_VERTEX_NUM];

//**************************************主函数main()********************************************
void main(void)
{ VertexType u;
  MGraph G;

  cout<<"*******************************************************"<<endl;
  cout<<"*          本程序的作用是求解最小生成树!              *"<<endl;
  cout<<"*******************************************************"<<endl;

  cout<<"现在来构造无向网G!"<<endl;
  CreateUDN(G);
  cout<<endl<<"无向网G已构造好!"<<endl;

  cout<<"请输入你要从哪个顶点出发来建立最小生成树: ";
  cin>>u;
  MiniSpanTree_PRIM(G,u);

  cout<<endl<<"程序至此结束!"<<endl;
}//main()

//**********************************函数CreateUDN()*********************************************

Status CreateUDN(MGraph &G)
{
	VertexType  v1,v2;
    VRType    w;
	int i,j,k;

	cout<<"请输入无向网G的顶点个数: ";
	cin>>G.vexnum;
	cout<<"请输入无向网G的弧的条数: ";
	cin>>G.arcnum;

	for (i=0;i<G.vexnum  ; i++)
	for (k=0;k<G.vexnum  ; k++)
		G.arcs[i][k].adj = 0 ;

    for(i=0;i<G.vexnum;i++)
	{cout<<"请输入第" <<i+1<< "个顶点值: ";
	cin>>G.vexs[i];}//for

	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			G.arcs[i][j].adj=INFINITY;

	for(k=0;k<G.arcnum;++k){
	cout<<"请输入一条边依附的顶点值及权值(权值为整数): ";
		cin>>v1>>v2>>w;
		i=LocateVex(G,v1);  j=LocateVex(G,v2);  //cout<<"\n"<<i<<" "<<j;
		G.arcs[i][j].adj=w;
		G.arcs[j][i].adj=G.arcs[i][j].adj;
	}//for


/*	for (i=0;i<G.vexnum  ; i++)
	{for (k=0;k<G.vexnum  ; k++)
		cout<<" "<<G.arcs[i][k].adj ;
	 cout << "\n";
	} */
	return OK;
}//CreateUDN()

//**************************************函数LocateVex()*****************************************

int  LocateVex(MGraph &G,VertexType u){
		int i;
		for(i=0;i<G.vexnum;i++)
			if(G.vexs[i]==u) return i;
		return -1;
	}//LocateVex()

//*************************************函数MiniSpanTree_PRIM***********************************

void MiniSpanTree_PRIM(MGraph &G,VertexType u)
{

	int i,j,k;

	k=LocateVex(G,u);

	for(j=0;j<G.vexnum;++j)
	if(j!=k)
		{closedge[j].adjvex = u;
		 closedge[j].lowcost=G.arcs[k][j].adj;}

	closedge[k].lowcost=0;

	cout<<"一棵最小生成树是:"<<endl;
	cout<<"{";
	for(i=1;i<G.vexnum;++i){
	k = minimum(G.vexnum); //     cout<<"slodlwo";
	cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<"),";
	closedge[k].lowcost=0;
		for(j=0;j<G.vexnum;++j)
			if( (G.arcs[k][j].adj>0)&&(G.arcs[k][j].adj<closedge[j].lowcost) )
			{closedge[j].adjvex = G.vexs[k];
			 closedge[j].lowcost= G.arcs[k][j].adj;
			}//if
	}//for
	cout<<"\b"<<"}";
}//MiniSpanTree

//************************************函数minimum()**********************************************

int minimum(int n){
	int i,k;
	VRType low_cost;

	for(i=0;i<n;i++)
		if(closedge[i].lowcost != 0 )
		{k=i;
		 low_cost=closedge[i].lowcost;
		 break;
		}//for
	for(i=0;i<n;i++)
		if ( (closedge[i].lowcost >0) && (closedge[i].lowcost<low_cost) )
		{low_cost=closedge[i].lowcost;k=i;}

	return k;
}//minimum()

//**************************************程序至此结束*********************************************

void Print_Graph(MGraph G){
	int i,k,vexnum,arcnum;

	vexnum = G.vexnum ;
	arcnum = G.arcnum ;

	cout<<"\n顶点的信息:"<<endl;
	for(i=0;i<vexnum;i++)
		cout<<G.vexs[i]<<endl;

	cout<<"\n边的信息:"<<endl;
	for(i=0;i<arcnum;i++)
	for(k=i+1;k<arcnum;k++)
	{
		if (G.arcs [i][k].adj != 0)
			cout<<G.vexs[i]<<" "<<G.vexs[k]<<" "<<G.arcs[i][k].adj ;
	};
}//Print_Graph