注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mihooke's blog

IT之恋

 
 
 

日志

 
 

图的深度优先遍历和广度优先遍历  

2014-07-27 18:29:08|  分类: 学习录 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
图的深度优先遍历和广度优先遍历 - mihooke - mihooke的博客

 //深度优先遍历

        这种遍历法类似于树的先序遍历,因为图的每个顶点(vertex)都可以作为出发点进行遍历,所以遍历的时候要先假设个出发点,这里假设v0为出发点,之后便选择邻接点v1,以此类推,先后遍历顶点v1v3v7。在访问完v7之后,由于v7的邻接点都已被访问,所以便回到顶点v4,继续搜索v4的邻接点,若v4的邻接点也都被访问完了,则继续上溯,直到回到顶点v0才开始访问v0的另一个邻接点v2,如此循环下去进行搜索。由此得到的访问序列是:

v0 -> v1 -> v3 -> v7 -> v4 -> v2 -> v5 -> v6

在这个算法中,我们要辨别哪些顶点被访问了,哪些还没被访问,这里用一个标识数组visited[],把其初始值设为false,访问过的顶点则设为true,便可确认。

#define MaxVertexNum 50

#define flase 0

#define true 1

typedef struct node{ //图作为一个表存储的结点域

   int adjvertex;

   int info;//边或弧上的信息

   struct node *next;

}EdgeNode;

int visited[MaxVertexNum];

void DFStraverse(ALGraph G)//G表示一个图,图作为参数传递进来

{

   int v;

   for(v=0;v<G.vertexNum;v++)

   visited[v]=flase;    //标识数组初始化为false

   for(v=0;v<G.vertexNum;v++)

   if(!visited[v])

      DFS(G,v); //调用遍历函数DFS

}

void DFS(ALGraph G,int v)

{

   EdgeNode *p;

   int w;

   printf("%c",v);

   visited[v]=true;

   for(p=G.adjlist[v].firstedge;p;p++)

   { //v顶点开始循环遍历

      w=p->adjvertex;

      if(!visited[v])

      DFS(G,V); //用递归的思想去实现全部遍历

   }

}

整个遍历过程就是对图的顶点和其邻接点查找的过程,因此耗费的时间取决于存储顶点的结构 /*有邻接矩阵和邻接表2中存储结构*/

//图的广度优先搜索遍历

广度优先搜索遍历类似于树的层次遍历。如上面的图,遍历结果就是:

v0  v1  v2  v3  v4  v5  v6   v7

广度优先搜索遍历和深度优先搜索遍历算法思想一样,但遍历次序不一样。根据存储结构的不同有两种算法实现。下面是以邻接表为存储结构的算法。

void BFS(ALGraph G,int v)

{

   EdgeNode *p;

   int u,v,w;

   PSeqQueue Q;  //用队列来存放遍历的顶点,队列定义参考文章末尾

   Q=Init_Seqqueue();

   printf("%c",v);

   visited[v]=true;

   In_Seqqueue(Q,V); //入队

   while(!Empty_seqqueue(Q))

   {

Out_seqqueue(Q,&u);

for(p=G.adjlist[u].firstedge;p;p=p->next)

{

   w=p->adjvertex;

   if(!visited[w])

   {

printf("%c",w);

visited[w]=true;

In_seqqueue(Q,w);//u的未访问的邻接点w入队

   }

}

   }

}

下面是以邻接矩阵为存储结构的算法。

void BFS(MGraph G){

   int v;

   for(v=0;v<G.vertexNum;v++){

   visited[v]=false;

}

   for(v=0;v<G.vertexNum;v++)

   if(!visited[v])

   BFS(G,V); //开始遍历

}

void BFS(MGraph G,int v)

{

   int i,j;

   PSeqqueue Q;

   Q=Init_Seqqueue();

   printf("%c",v);

   visited[v];

   In_Sqqueue(Q,v);

   while(!Empty_Seqqueue(Q)){

      Out_Seqqueue(Q,v);

      for(j=0;j<G.vertexNum;j++)//依次搜索j的邻接点

        if(G.arcs[i][j]==1&&!visited[j]){//邻接矩阵元素

          printf("%c",j);

          visited[j]=true;

          In_Seqqueue(Q,j);

        }

   }

}

//邻接表

typedef struct {

   VertexNode adjlist[MaxVertexNum];

   int vertexNum,edgeNum;

}ALGraph;

//邻接矩阵

typedef struct {

   VertexType vertex[MaxVertexNum];

   Edgetype arcs[MaxVertexNum][MaxVertexNum];

   int vertexNum,edgeNum;

}MGraph;

//队列

#define MAX 100

typedef struct {

   int data[MAX];

   int front,rear; //队头队尾指针

}Seqqueue,*PSeqqueue;

//初始化队列

PSeqqueue Init_Seqqueue(){

   PSeqqueue Q;

   Q=(PSeqqueue)malloc(sizeof(Seqqueue));

   if (Q){

      Q->front=0;

      Q->rear=0;

   }

   return Q;

}

//判断队空

int Empty_Seqqueue(PSeqqueue Q){

   if(Q && Q->front==Q->rear)

      return 1;

   else

      return 0;

}

//入队

int In_Seqqueue(PSeqqueue Q,DataType x){

   if((Q->rear+1)%MAX==Q->front){

      printf("queue is full!");

      return -1;

}

   else{

      Q->rear=(Q->rear+1)%MAX;

      Q->data[Q->rear]=x;

      return 1;

   }

}

//出队

int Out_Seqqueue(PSeqqueue Q,DataType x){

   if(Empty_Seqqueue(Q)){

      printf("queue is empty!");

      return -1;

   }

   else{

      Q->front=(Q->front+1)%MAX;

      *x=Q->data[Q->front];

      return 1;

   }

}

  评论这张
 
阅读(35)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017