1. 全栈程序员必看首页

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

全栈程序员-用户IM • • 未分类

写这个程序给我的感觉就是乱，思路不是很清晰，遍历的逻辑关系还掌握的不是很熟，只是大概知道是这么回事，但是让自己去写的话，可能就写不出来了！还是要加大对遍历的熟悉程度才行啊！PS：另外推荐一个让大家真

大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。

/*图的存储及遍历*/  
#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);  
}

写这个程序给我的感觉就是乱，思路不是很清晰，遍历的逻辑关系还掌握的不是很熟，只是大概知道是这么回事，但是让自己去写的话，可能就写不出来了！还是要加大对遍历的熟悉程度才行啊！

 

PS：另外推荐一个让大家真正练手的网站：猪八戒威客网，在这里可以按自己的能力去接一些程序设计的任务。我觉得这是一种很不错的学习方法，当你接了别人的任务，无形中就给了自己压力和动力，然后就会主动的去查询资料，分析问题，可能会历经艰辛才能解决问题，但这中间的过程是很珍贵的，你会通过自己的努力学到很多课本上没有学到的东西，也能过一回需求分析的瘾，真实的体会到和客户进行交流的诸多“纠结”，最后，如果你的努力得到客户的认可，可以获得一笔小小的佣金，当做对自己的奖励，更重要的是，通过做任务，你能体会到自己存在的价值感和对自己能力的肯定！

推荐：http://www.cnblogs.com/roucheng/p/cpphong.html

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/120468.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号