VC++2012编程演练数据结构《29》图

大灰狼

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
　　在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。
　　在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi,vj>，它表示从顶点vi到顶点vj有一条边。
　　若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和<vj,vi>两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧，我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。
　　路径长度是指路径上边或弧的数目。
　　若第一个顶点和最后一个顶点相同，则这条路径是一条回路。
　　若路径中顶点没有重复出现，则称这条路径为简单路径。
　　在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。
　　在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
图的基本操作
　　（1）创建一个图结构 CreateGraph(G)
　　（2）检索给定顶点 LocateVex(G,elem)
　　（3）获取图中某个顶点 GetVex(G,v)
　　（4）为图中顶点赋值 PutVex(G,v,value)
　　（5）返回第一个邻接点 FirstAdjVex(G,v)
　　（6）返回下一个邻接点 NextAdjVex(G,v,w)
　　（7）插入一个顶点 InsertVex(G,v)
　　（8）删除一个顶点 DeleteVex(G,v)
　　（9）插入一条边 InsertEdge(G,v,w)
　　（10）删除一条边 DeleteEdge(G,v,w)

　　（11）遍历图 Traverse(G,v)

d打开ＩＤＥ

我们来创建一个工程

类的声名如下

[cpp] view plaincopy

• #if !defined(AFX_GRAPH_H__DB7A5E72_86CB_45E7_B575_00831A6D3C5F__INCLUDED_)  
• #define AFX_GRAPH_H__DB7A5E72_86CB_45E7_B575_00831A6D3C5F__INCLUDED_  
•   
• #if _MSC_VER > 1000  
• #pragma once  
• #endif // _MSC_VER > 1000  
•   
• //图的相关数据类型的定义graph.h  
• //最多顶点数  
• const int MaxV=10;  
• //最大权值  
• const int MaxValue=99;  
• //定义邻接表中的边结点类型  
• struct edgenode {  
•     int adjvex;   //邻接点域  
•     int weight;   //权值域  
•     edgenode* next;//指向下一个边结点的链域  
• };  
• //定义邻接表类型  
• typedef edgenode** adjlist;  
• //邻接矩阵类定义  
• class AdjMatrix  
• {private:  
• char g[MaxV];//顶点信息数组  
• int size;//当前顶点数  
• int GA[MaxV][MaxV];//定义邻接矩阵GA  
• int numE;//当前边数  
• public:  
•     //构造函数,初始化图的邻接矩阵  
•     AdjMatrix(int n,int k2);  
•     //判断图空否  
•     bool GraphEmpty() {return size==0;}  
•     //取当前顶点数  
•     int NumV() {return size;}  
•     //取当前边数  
•     int NumEdges() {return numE;}  
•     //取顶点i的值  
•     char GetValue(const int i);  
•     //取弧<v1,v2>的权  
•     int GetWeight(const int v1,const int v2);  
•     //在位置pos处插入顶点V  
•     void InsertV(const char &V,int pos);  
•     //插入弧<v1,v2>,权为weight  
•     void InsertEdge(const int v1,const int v2,int weight);  
•     //删除顶点i与顶点i相关的所有边  
•     char DeleteVE(const int i);  
•     //删除弧<v1,v2>  
•     void DeleteEdge(const int v1,const int v2);  
•     //建立图的邻接矩阵  
•     void CreateMatrix(int n, int k1,int k2);  
•     //k1为0则无向否则为有向,k2为0则无权否则为有权  
•     //从初始点vi出发深度优先搜索由邻接矩阵表示的图  
•     void dfsMatrix(bool*& visited,int i,int n,int k2);  
•     //从初始点vi出发广度优先搜索由邻接矩阵表示的图  
•     void bfsMatrix(bool*& visited,int i,int n,int k2);  
•     //由图的邻接矩阵得到图的邻接表  
•     void graphChange(adjlist &GL,int n,int k2);  
•     //检查输入的边序号是否越界,若越界则重输  
•     void Check(int n,int& i,int& j);  
•     //由图的邻接矩阵建立图  
•     void Creatgraph(int n,int k2);  
•     //对非连通图进行深度优先搜索  
•     void dfsMatrix(int n,int k2);  
•     //对非连通图进行广度优先搜索  
•     void bfsMatrix(int n,int k2);  
• };  
•   
• #endif // !defined(AFX_GRAPH_H__DB7A5E72_86CB_45E7_B575_00831A6D3C5F__INCLUDED_)  
  

类的实现如下

[cpp] view plaincopy

• #include "stdafx.h"  
•   
• //图的相关运算的实现graph.cpp  
• #include "graph.h"  
• //构造函数,初始化图的邻接矩阵  
• AdjMatrix::AdjMatrix(int n,int k2)  
• {int i,j;  
• if(k2==0){//初始化无(有)向无权图  
•   for(i=0;i<n;i++)  
•    for(j=0;j<n;j++)  
•     GA[j]=0;}  
• else {//初始化无(有)向有权图  
•   for(i=0;i<n;i++)  
•    for(j=0;j<n;j++)  
•     if(i==j) GA[j]=0;  
•     else GA[j]=MaxValue;}  
• size=numE=0;  
• }  
• //建立图的邻接矩阵  
• void AdjMatrix::CreateMatrix(int n,int k1,int k2)  
• //k1为0则无向否则为有向,k2为0则无权否则为有权  
• {int i,j,k,e,w;  
• cout<<"输入图的总边数:";  
•    cin>>e;  
• if(k1==0 && k2==0) { //建立无向无权图  
•   cout<<"输入"<<e<<"条无向无权边的起点和终点序号!"<<endl;  
•   for(k=1; k<=e; k++) {  
•    cin>>i>>j;  
•    Check(n,i,j);  
•    GA[j]=GA[j]=1;}  
•   }  
• else if(k1==0 && k2!=0) { //建立无向有权图  
•    cout<<"输入"<<e<<"条无向带权边的起点和终点序号及权值!"<<endl;  
•    for(k=1; k<=e; k++) {  
•     cin>>i>>j>>w;  
•     Check(n,i,j);  
•     GA[j]=GA[j]=w;}  
•   }  
•   else if(k1!=0 && k2==0) { //建立有向无权图  
•     cout<<"输入"<<e<<"条有向无权边的起点和终点序号!"<<endl;  
•     for(k=1; k<=e; k++) {  
•      cin>>i>>j;  
•      Check(n,i,j);  
•      GA[j]=1;}  
•   }  
•   else if(k1!=0 && k2!=0) { //建立有向有权图  
•     cout<<"输入"<<e<<"条有向有权边的起点和终点序号及权值!"<<endl;  
•     for(k=1; k<=e; k++) {  
•      cin>>i>>j>>w;  
•      Check(n,i,j);  
•      GA[j]=w;}}  
•   numE=e;     
•   cout<<"创建后的邻接矩阵:\n";     
•   for(i=0;i<n;i++)  
•   {for(j=0;j<n;j++)  
•     cout<<setw(4)<<GA[j];  
•    cout<<endl;}  
• }  
• //从初始点vi出发深度优先搜索由邻接矩阵表示的图  
• void AdjMatrix::dfsMatrix(bool*& visited,int i,int n,int k2)  
• {cout<<g<<':'<<i<<"  ";  
• visited=true;        //标记vi已被访问过  
• for(int j=0; j<n; j++)  //依次搜索vi的每个邻接点  
•   if(k2==0)  
•    {if(i!=j&&GA[j]!=0&&!visited[j])  
•      dfsMatrix(visited,j,n,k2);}  
•   else  
•    if(i!=j&&GA[j]!=MaxValue&&!visited[j])  
•      dfsMatrix(visited,j,n,k2);  
• }  
• //从初始点vi出发广度优先搜索由邻接矩阵表示的图  
• void AdjMatrix::bfsMatrix(bool*& visited,int i,int n,int k2)  
• {const int MaxLength=30;  
• //定义一个队列q,其元素类型应为整型  
• int q[MaxLength]={0};  
• //定义队首和队尾指针  
• int front=0,rear=0;  
• //访问初始点vi  
• cout<<g<<':'<<i<<"  ";  
• //标记初始点vi已访问过  
• visited=true;  
•   //将已访问过的初始点序号i入队  
• q[++rear]=i;  
•   //当队列非空时进行循环处理  
• while(front!=rear) {  
•   //删除队首元素,第一次执行时k的值为i  
•   front=(front+1)%MaxLength;  
•   int k=q[front];  
•   //依次搜索vk的每一个可能的邻接点  
•   for(int j=0;j<n;j++)  
•    if(k2==0)  
•     {if(k!=j&&GA[k][j]!=0&&!visited[j])  
•      {//访问一个未被访问过的邻接点vj  
•       cout<<g[j]<<':'<<j<<"  ";  
•       visited[j]=true;     //标记vj已访问过  
•       rear=(rear+1)%MaxLength;//顶点序号j入队  
•       q[rear]=j;  
•      }  
•     }  
•    else  
•     if(k!=j&&GA[k][j]!=MaxValue&&!visited[j])  
•      {//访问一个未被访问过的邻接点vj  
•       cout<<g[j]<<':'<<j<<"  ";  
•       visited[j]=true;   //标记vj已访问过  
•       rear=(rear+1)%MaxLength;//顶点序号j入队  
•       q[rear]=j;  
•      }  
• }}  
• //检查输入的边序号是否越界,若越界则重输  
• void AdjMatrix::Check(int n,int& i,int& j)  
• {while(1) {  
•   if(i<0||i>=n||j<0||j>=n)  
•     cout<<"输入有误,请重输!";  
•   else return;  
•   cin>>i>>j;  
• }  
• }  
• //由图的邻接矩阵得到图的邻接表  
• void AdjMatrix::graphChange(adjlist &GL,int n,int k2)  
• {int i,j;  
• if(k2==0)  
• {for(i=0;i<n;i++){  
•   for(j=0;j<n;j++)  
•     if(GA[j]!=0) {  
•      edgenode* p=new edgenode;  
•      p->adjvex=j;  
•      p->next=GL;GL=p;  
•      cout<<'('<<i<<','<<p->adjvex<<") ";}  
•   cout<<endl;}}  
• else {  
•   for(i=0;i<n;i++){  
•    for(j=0;j<n;j++)  
•     if(GA[j]!=0 && GA[j]!=MaxValue) {  
•      edgenode* p=new edgenode;  
•      p->adjvex=j;p->weight=GA[j];  
•      p->next=GL;GL=p;  
•      cout<<'('<<i<<','<<p->adjvex<<','<<p->weight<<") ";}  
•    cout<<endl;}  
• }}  
• //由图的邻接矩阵建立图  
• void AdjMatrix::Creatgraph(int n,int k2)  
• {int i,j,k,m=0;  
• if(k2==0)  
• {for(i=0;i<n;i++){  
•    k=i;  
•   for(j=0;j<n;j++)  
•     if(GA[j]!=0)  
•      if(k==i&&m<n)  
•       {g[m]='A'+m;size++;  
•        cout<<g[m]<<'('<<i<<','<<j<<") ";  
•        m++;  
•       }  
•   }  
•   cout<<endl;}  
• else {  
•   for(i=0;i<n;i++){  
•    k=i;  
•    for(j=0;j<n;j++)  
•     if(GA[j]!=0 && GA[j]!=MaxValue)  
•      if(k==i&&m<n)  
•       {g[m]='A'+m;size++;  
•        cout<<g[m]<<'('<<i<<','<<j<<','<<GA[j]<<") ";  
•        m++;  
•       }  
•   }  
• cout<<endl;}  
• g[n]='\0';  
• }  
• //取顶点i的值  
• char AdjMatrix::GetValue(const int i)  
• {if(i<0||i>size)  
•   {cerr<<"参数i越界!\n";exit(1);}  
• return g;  
• }  
• //取弧<v1,v2>的权  
• int AdjMatrix::GetWeight(const int v1,const int v2)  
• {if(v1<0||v1>size||v2<0||v2>size)  
•   {cerr<<"参数v1或v2越界!\n";exit(1);}  
• return GA[v1][v2];   
• }  
• //在位置pos处插入顶点V  
• void AdjMatrix::InsertV(const char &V,int pos)  
• {int i;  
• if(size==MaxV)  
•   {cerr<<"表已满,无法插入!\n";exit(1);}  
• if(pos<0||pos>size)  
•   {cerr<<"参数pos越界!\n";exit(1);}  
• for(i=size;i>pos;i--) g=g[i-1];  
• g[pos]=V;  
• size++;   
• }  
• //插入弧<v1,v2>,权为weight  
• void AdjMatrix::InsertEdge(const int v1,const int v2,int weight)  
• {if(v1<0||v1>size||v2<0||v2>size)  
•   {cerr<<"参数v1或v2越界!\n";exit(1);}  
• GA[v1][v2]=weight;  
• numE++;   
• }  
• //删除顶点v与顶点v相关的所有边  
• char AdjMatrix::DeleteVE(const int v)  
• {for(int i=0;i<size;i++)  
•   for(int j=0;j<size;j++)  
•    if((i==v||j==v)&&GA[j]>0&&GA[j]<MaxValue)  
•     {GA[j]=MaxValue;  
•      numE--;}  
• if(size==0)  
•   {cerr<<"表已空,无元素可删!\n";exit(1);}  
• if(v<0||v>size-1)  
•   {cerr<<"参数v越界!\n";exit(1);}  
• char temp=g[v];  
• for(int i=v;i<size-1;i++) g=g[i+1];  
• size--;  
• g[size]='\0';  
• return temp;  
• }  
• //删除弧<v1,v2>  
• void AdjMatrix::DeleteEdge(const int v1,const int v2)  
• {if(v1<0||v1>size||v2<0||v2>size||v1==v2)  
•   {cerr<<"参数v1或v2出错!\n";exit(1);}  
• GA[v1][v2]=MaxValue;  
• numE--;  
• }  
• //对非连通图进行深度优先搜索  
• void AdjMatrix::dfsMatrix(int n,int k2)  
• {bool *vis=new bool[NumV()];  
• for(int i=0;i<NumV();i++) vis=false;  
• for(int i=0;i<NumV();i++)  
•   if(!vis) dfsMatrix(vis,i,n,k2);  
• delete []vis;  
• }  
• //对非连通图进行广度优先搜索  
• void AdjMatrix::bfsMatrix(int n,int k2)  
• {bool *vis=new bool[NumV()];  
• for(int i=0;i<NumV();i++) vis=false;  
• for(int i=0;i<NumV();i++)  
•   if(!vis) bfsMatrix(vis,i,n,k2);  
• delete []vis;  
• }  
  

代码调用如下

[cpp] view plaincopy

• #include "stdafx.h"  
•   
• #include "graph.h"  
• void main()  
• {cout<<"graphM.cpp运行结果:\n";  
• //定义图的点数及搜索起始点序号等  
• int n,k,i;  
• //k1为0则无向否则为有向,k2为0则无权否则为有权  
• int k1,k2;  
• //标记已访问过的点  
• bool *vis;  
• //定义邻接表  
• adjlist AL;  
• cout<<"输入图的点数n=";cin>>n;  
• AL=new edgenode*[n];  
• vis=new bool[n];  
• if(!vis) {cout<<"申请堆内存失败!\n";exit(1);}  
• for(i=0;i<n;i++)  
•      vis=false;  
• cout<<"输入选择无向(权)与有向(权)图的值k1,k2:";  
• cin>>k1>>k2;  
• //定义邻接矩阵  
• AdjMatrix A(n,k2);  
• A.CreateMatrix(n,k1,k2);  
• cout<<"出发点Vk的序号=";cin>>k;  
• cout<<"\n输出邻接矩阵相应图的每个顶点:\n";  
• A.Creatgraph(n,k2);  
• cout<<"当前的顶点数为:"<<A.NumV()<<endl;  
• cout<<"当前的边数为:"<<A.NumEdges()<<endl;  
•    
• cout<<"图的深度优先搜索顺序:\n";  
• A.dfsMatrix(vis,k,n,k2);  
• for(i=0;i<n;i++) vis=false;  
• cout<<"\n图的广度优先搜索顺序:\n";  
• A.bfsMatrix(vis,k,n,k2);  
•    
• cout<<"\n输出邻接表的每个邻接点:\n";  
• for(i=0;i<n;i++) vis=false;  
• A.graphChange(AL,n,k2);  
• delete []vis;  
•    
• A.DeleteEdge(0,2);  
• A.DeleteEdge(2,0);  
•    
• cout<<"当前的顶点数为:"<<A.NumV()<<endl;  
• cout<<"当前的边数为:"<<A.NumEdges()<<endl;  
• cout<<"图的深度优先搜索顺序:\n";  
• A.dfsMatrix(n,k2);  
• cout<<"\n图的广度优先搜索顺序:\n";  
• A.bfsMatrix(n,k2);  
• cin.get();cin.get();  
• }  
  

效果如下