两种遍历图的方法.cpp

熟悉图的两种常用的存储结构

#include <iostream.h>
#include <conio.h>
#include <iomanip.h>
const int MaxVertices=10;
const int MaxWeight=10000;
struct MinSpanTree              //带权边的三个参数
{  int begin,end;              //边的起点与终点
     float length;                 //边的权值
};
class  AdjMWGraph
{ private:
	  int  Vertices[10];                     //顶点信息的数组
	  int  Edge[MaxVertices][MaxVertices];   //边的权信息的矩阵
	  int  numE;                             //当前的边数
int  numV;                             //当前的顶点数
public:
AdjMWGraph();      				//构造函数
  void  CreatG(int n,int e);
  void  PrintOut();
  void  Prim() ;						//求最小生成树方法
};
AdjMWGraph::AdjMWGraph()        //构造函数
{ for ( int i=0; i<MaxVertices; i++ )
      for ( int j=0; j<MaxVertices; j++ )
      	{ if( i==j )  Edge[i][j]=0;
        	else   Edge[i][j]=MaxWeight; //MaxWeight表示无穷大
        }
  numE=0;                         //当前边个数初始为0
  numV=0;
}
void  AdjMWGraph::CreatG(int n,int e)
{ int vi,vj,w;
 numE=e;   numV=n;
 cout<<"\n  输入顶点的信息（整型）：" ;
 for (int i=0; i<numV; i++ )
    { cout<<"\n "<<i+1<<": ";
        cin>>Vertices[i];
    }
 for ( int i=0; i<numE; i++ )
    { cout<<"\n  输入边的信息（vi,vj,W）：";
      cin>>vi>>vj>>w;
      Edge[vi-1][vj-1]=w; Edge[vj-1][vi-1]=w;   //对于无向图
    }
 }
void AdjMWGraph::PrintOut()
{ cout<<"\n  输出顶点的信息（整型）：\n";
  for ( int i=0; i<numV; i++ )cout<<Vertices[i]<<"  ";
  cout<<"\n  输出邻接矩阵 ：" ;
  for (int i=0; i<numV; i++ )
       { cout<<"\n "<<i+1<<": ";
         for ( int j=0; j<numV ;j++ )
         cout<<Edge[i][j]<<"  ";
         cout<<endl;
       }
 }
void  AdjMWGraph::Prim ()
{  int  n=numV,m,v;                      //顶点总数
   MinSpanTree e, mintree[MaxVertices];         // mintree 生成树数组
   for (int j=1; j<n; j++)                 //初始化tree[n-1]
     { mintree[j-1].begin=1;             //顶点1并入U
       mintree[j-1].end=j+1;
       mintree[j-1].length=Edge[0][j];    // G.Edge[][]是连通网的带权邻接矩阵
    }
  for (int k=0; k<n-1; k++)              // 求第k+1条边
   { int min=MaxWeight;
     for (int j=k; j<n-1; j++)
     if (mintree[j].length<min )  {min=mintree[j].length;  m=j;}
     e=mintree[m]; mintree[m]=mintree[k];  mintree[k]=e;
     v=mintree[k].end;               /*V∈U*/
     for (int j=k+1;  j<n-1;  j++)      //在新的顶点v并入U之后更新tree[n-1]
      { int d=Edge[v-1][mintree[j].end-1];
        if (d<mintree[j].length)  {  mintree[j].length=d;
                                     mintree[j].begin=v;
                                   }
     } //for j
    }// for k
  for (int j=0;j<n-1; j++)
cout<<"\n"<<"起点："<<mintree[j].begin<<"     终点："<<
mintree[j].end<<"    权值："<<mintree[j].length;
  }
int main(int argc, char* argv[])
{ AdjMWGraph  G ;    int n,e;
  cout<<"\n  请输入图的总顶点数和总边数（n,e=?）：";  cin>>n>>e ;
  G.CreatG(n,e);    G.PrintOut();
  cout<<"最小生成树如下";
  cout<<"共有"<<n-1<<"条边" ;
  G.Prim();  _getch();  return 0;
}