图的存储及遍历 深度遍历和广度遍历 C++代码实现

/*图的存储及遍历*/  
#include<iostream>  
using namespace std;  
//-----------------------------------  
//邻接矩阵的存储及深度和广度遍历  
//-----------------------------------  
   
/*邻接矩阵的类型定义*/  
#define MAX 10000000  
#define MAX_VERTEX_NUM 20  
typedef enum{ DG,DN,UDG,UDN }GraphKind;//有向图，有向网，无向图，无向网  
typedef struct  
{  
       char vexs[MAX_VERTEX_NUM];//用一维数组存储顶点信息  
       int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//用二维数组充当矩阵，来存储顶点边的信息  
       int vexnum,edgenum;//顶点树和边数  
       GraphKind kind;//图的种类  
}MGraph;  
   
/*构造无向图的邻接矩阵*/  
void CreateUDG_AM(MGraph &G,int n,int e)  
{  
       G.vexnum=n;  
       G.edgenum=e;  
        
       int i,j,k;  
       for(i=0;i<n;i++)  
              cin>>G.vexs[i];//输入顶点信息  
   
       for(i=0;i<n;i++)  
              for(j=0;j<n;j++)  
                     G.edges[i][j]=0;//将矩阵初始化为0  
   
       for(k=0;k<e;k++)  
       {  
              cin>>i>>j;//这里只用输入对称的边就行，也就是输入下矩阵或是上矩阵  
              G.edges[i][j]=G.edges[j][i]=1;//输入边的信息  
       }  
}  
   
/****************************无向图的深度优先遍历************************/  
int visited[MAX_VERTEX_NUM];  
   
void DF_AM(MGraph &G,int i)  
{  
       int j;  
       cout<<G.vexs[i]<<" ";  
       visited[i]=1;  
       for(j=0;j<G.vexnum;j++)  
       {  
              if((G.edges[i][j])==1&&(visited[j])==0)  
                     DF_AM(G,j);  
       }  
}  
   
void DF_Traverse_AM(MGraph &G)  
{  
       int i;  
       for(i=0;i<G.vexnum;i++)  
       {  
              visited[i]=0;  
       }  
       for(i=0;i<G.vexnum;i++)  
       {  
              if(!visited[i])  
                     DF_AM(G,i);  
       }  
}  
   
/*********************无向图的广度优先遍历*****************************/  
   
//循环队列的类型定义  
const int Queue_Size=100;  
   
typedef struct circlQueue  
{  
       int *elem;  
       int rear;  
       int front;  
       int queueSize;  
}circlQueue;  
   
//初始化  
void initQueue_C(circlQueue &Q)  
{  
       Q.elem=new int[Queue_Size];  
       Q.front=Q.rear=0;//首尾指针相等说明队列为空。  
       Q.queueSize=Queue_Size;  
}  
   
//入队列  
void enterQueue_C(circlQueue &Q,int x)  
{  
       if(((Q.rear+1)%Q.queueSize)==Q.front)//判断栈满的情况  
              cout<<"Queue OverFlow!";  
       Q.elem[Q.rear]=x;  
       Q.rear=(Q.rear+1)%Queue_Size;//尾指针应以此种方式加1，才会实现循环队列。  
}  
   
//出队列  
char outputQueue_C(circlQueue &Q)  
{  
       int e;  
       if(Q.rear==Q.front)  
              cout<<"Queue Empty";  
       e=Q.elem[Q.front];  
       Q.front=(Q.front+1)%Q.queueSize;;//头指针应以此种方式加1，才会实现循环队列。  
       return e;  
}  
//广度遍历  
void BF_Traverse_AM(MGraph &G)  
{  
       int i,j,v;  
       for(i=0;i<G.vexnum;i++)  
              visited[i]=0;  
       circlQueue Q;  
       initQueue_C(Q);//队列实现了“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问  
       for(i=0;i<G.vexnum;i++)  
       {  
              if(!visited[i])  
              {  
                     cout<<G.vexs[i]<<" ";  
                     visited[i]=1;  
                     enterQueue_C(Q,i);  
                     while(Q.front!=Q.rear)  
                     {//这个循环是将队列里面的顶点取出来，然后进行下面的for循环  
                            v=outputQueue_C(Q);  
                            for(j=0;j<G.vexnum;j++)  
                            {//这个循环是将顶点的全部邻接点依次访问并且入队列  
                                   if(G.edges[v][j]&&(!visited[j]))  
                                   {  
                                          cout<<G.vexs[j]<<" ";  
                                          visited[j]=1;  
                                          enterQueue_C(Q,j);  
                                   }  
                            }  
                     }  
              }  
       }  
}  
   
//-----------------------------------------------  
//邻接表的存储及深度和广度遍历  
//-----------------------------------------------  
typedef struct EdgeNode  
{//边表结点的定义  
       int adjvex;//存放邻接点在顶点表中的位置  
       struct EdgeNode * nextedge;//指向下一个边表结点  
       int weight;  
}EdgeNode;  
   
typedef struct VexNode  
{//顶点表结点的定义  
       char vex;//存放顶点信息  
       EdgeNode * firstedge;//指向第一个边表结点  
}VexNode;  
   
typedef struct  
{//顶点表的定义    
       VexNode vexs[MAX_VERTEX_NUM];  
       int vexnum,edgenum;  
       GraphKind kind;  
}LGraph;  
   
/*构造有向图的邻接表*/  
void CreateDG_AL(LGraph &G,int n,int e)  
{  
       int i,j,k;  
       G.vexnum=n;  
       G.edgenum=e;  
       G.kind=DG;  
       for(i=0;i<n;i++)  
       {  
              cin>>G.vexs[i].vex;  
              G.vexs[i].firstedge=NULL;//初始化为空  
       }  
       for(k=0;k<e;k++)  
       {  
              EdgeNode *p;  
              cin>>i>>j;  
              p=new EdgeNode;  
              p->adjvex=j;  
              p->nextedge=G.vexs[i].firstedge;  
              G.vexs[i].firstedge=p;//采用头插法  
       }  
}  
   
/*********************有向图的深度优先遍历**************************/  
void DF_AL(LGraph &G,int v)  
{  
       int j;  
       EdgeNode *p;  
       cout<<G.vexs[v].vex<<" ";  
       visited[v]=1;  
       for(p=G.vexs[v].firstedge;p;p=p->nextedge)  
       {  
              j=p->adjvex;  
              if(!visited[j])  
                     DF_AL(G,j);  
       }  
}  
   
void DF_Traverse_AL(LGraph &G)  
{  
       int i;  
       for(i=0;i<G.vexnum;i++)  
       {  
              visited[i]=0;  
       }  
       for(i=0;i<G.vexnum;i++)  
       {  
              if(!visited[i])  
                     DF_AL(G,i);  
       }  
}  /* 何问起 hovertree.com */
/*********************有向图的广度优先遍历**************************/  
void BF_Traverse_AL(LGraph &G)  
{  
       int i,j,v;  
       EdgeNode *p;  
       for(i=0;i<G.vexnum;i++)  
              visited[i]=0;  
       circlQueue Q;  
       initQueue_C(Q);//队列实现了“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问  
       for(i=0;i<G.vexnum;i++)  
       {  
              if(!visited[i])  
              {  
                     cout<<G.vexs[i].vex<<" ";  
                     visited[i]=1;  
                     enterQueue_C(Q,i);  
                     while(Q.front!=Q.rear)  
                     {//这个循环是将队列里面的顶点取出来，然后进行下面的for循环  
                            v=outputQueue_C(Q);  
                            for(p=G.vexs[v].firstedge;p;p=p->nextedge)  
                            {//这个循环是将顶点的全部邻接点依次访问并且入队列  
                                   j=p->adjvex;  
                                   if(!visited[j])  
                                   {  
                                          cout<<G.vexs[j].vex<<" ";  
                                          visited[j]=1;  
                                          enterQueue_C(Q,j);  
                                   }  
                            }  
                     }  
              }  
       }  
}  
void main()  
{  
       /*MGraph G; 
       CreateUDG_AM(G,6,6); 
       DF_Traverse_AM(G); 
       cout<<endl; 
       BF_Traverse_AM(G);*/  
   
       LGraph G;  
       CreateDG_AL(G,5,7);  
       DF_Traverse_AL(G);  
       cout<<endl;  
       BF_Traverse_AL(G);  
}