graph.cpp

大二上学期期末的课程设计,自己做的比较详细,花了很多时间,与大家分享一下,希望大家也有好的程序借鉴.

#include"graph.h"
#include<iostream>
#include<string>
using namespace std;
MGraph::MGraph(char a[], int n, int e)      //a[]由just_do_it()函数实现初始化
{
  //cout<<"有向图邻接矩阵的初始化"<<endl<<endl;
  vertexNum=n;                  //顶点数
  arcNum=e;                     //边数
  int i,j,k,weight;
for (i=0; i<vertexNum; i++) 
  vertex[i]=a[i];
 for (i=0; i<vertexNum; i++)       //初始化邻接矩阵
	 for (j=0; j<vertexNum; j++)
         if(i==j)  arc[i][j]=0;
		 else arc[i][j]=999;      //以权值为999标记两点之间无有向边连接

		 cout<<endl<<"输出初始化的矩阵"<<endl;
         coutjuzhen();
         cout<<endl;
		cout<<"有向图邻接矩阵的构造----已知有向图边数为: "<<e<<endl;
        cout<<"修改邻接矩阵, 输入修改边的始末顶点序号及权值(weight): ";
   for (k=0; k<arcNum; k++)       //依次输入每一条边，并修改邻接矩阵的相应元素
	   {
          
          cin>>i>>j>>weight;                     //边依附的两个顶点的序号及边上的权值
		  cout<<"("<<i<<","<<j<<")"<<"->"<<weight<<"  ";
		 // cin>>weight;
		  arc[i][j]=weight;    //此处xxx为两点之间的边的权值,有待初始化.......

       }
   cout<<endl;
   cout<<"经修改后的邻接矩阵为:"<<endl;
      coutjuzhen();            //输出修改后的邻接矩阵
}

void MGraph::coutjuzhen()
{
 for (int i=0; i<vertexNum; i++)    
	{ 
	   for (int j=0; j<vertexNum; j++)
	   {  printf("%5d",arc[i][j]);  }   //为了输出对齐,此处用了C语言中的输出函数 printf()
    cout<<endl;
    }

}

void Dijkstra(MGraph G, int v)   
{
    int dist[12];
	char s[12];
    string  path[12]; 
	string  a;
	a=G.vertex[v];
    for (int i=1; i<G.vertexNum; i++)     //初始化dist[n]、path[n]
    {  
       dist[i]=G.arc[v][i];
       if (dist[i]!=999)  path[i]=a+G.vertex[i];
          else path[i]="";
    }
    s[0]=G.vertex[v];                    //初始化集合S
    dist[v]=0;                          //标记顶点v为源点
int num=1;
    cout<<endl<<"输出从始点到达各顶点的最短路径及其路径长度"<<endl;
  while (num<G.vertexNum)               //当数组s中的顶点数小于图的顶点数时循环
  {
   int k=G.vertexNum-1;
   for (i=0; i<G.vertexNum; i++)            //在dist中查找最小值元素
           if ((dist[i]<dist[k]) && dist[i]!=0 )   k=i;
		if (path[k]=="")  cout<<"无法到达"<<endl;   
        else cout<<"    "<<dist[k]<<"<--------"<<path[k]<<endl;
        s[num++]= G.vertex[k];                //将新生成的终点加入集合S
     	int kkk=dist[k];                   //kkk记录此时的始点与终点的路径长度
        dist[k]=0;                           //置顶点Vk为已生成终点标记
        for (i=0; i<G.vertexNum; i++)            //修改数组dist和path
           if (dist[i]>dist[k]+G.arc[k][i]) {
                                 dist[i]=kkk+G.arc[k][i];
                                 path[i]=path[k]+G.vertex[i];
           }
  }
}


void just_do_it()
{
    int vernum,edge ;
	char chnum[MaxSize];
	cout<<"***************************课程设计-2    最短路径问题**************************"<<endl;
	cout<<"请输入顶点数(vernum): ";    	cin>>vernum;  //各顶点的输入
	
    cout<<"请输入图中的各顶点(chnum[]): ";	
	for(int i=0;i<vernum;i++)	  cin>>chnum[i];       
	
	cout<<"请输入图中的边数(edge): ";  cin>>edge;
	MGraph check(chnum,vernum,edge);
	Dijkstra(check,0);         //全邻接数组中编号为'0'的顶点查找最短路径
	cout<<"***************************thank you for your spanning*************************"<<endl;
}