【软考】图的深度及广度遍历

   深度遍历利用递归函数，也可以用栈实现深度遍历，我觉得可以用递归的地方就可以用栈的，两种方法的运行顺序是一样的，但栈的效率更高些。

   广度遍历利用队列实现

   在本程序中建立的图如下：
   共有9个顶点，14条边为：
98，95，81，75，65，63，60，51，43，42，30，21，20，10
   所以程序中建立图的数据为：


 
   运行结果：
   可以看出深度遍历是沿着一条路探索到最深层，再回溯再换另一条路，而广度遍历利用队列的先进后出可以实现从里层开始一层一层的向外探索
   以下是代码：
   分为三部分：队列结构、图结构（多重表）、深度广度遍历   队列结构：
#include<iostream.h>

//定义状态代码及数据类型
#defineNULL0
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineINFINITY255
#defineMAX_VERTEX_NUM20

typedefintStatus;
typedefintElemType;

//-----------------------队列结构-------------------------

//节点存储结构
typedefstructQNode{
  ElemTypedata;
  structQNode*next;
}QNode,*QueuePtr;


//队列
typedefstruct{
  QueuePtrfront;
  QueuePtrrear;
}LinkQueue;

//初始化队列
StatusInitQueue(LinkQueue&Q){
  Q.front=Q.rear=newQNode;
  if(!Q.front)
    returnERROR;
  Q.front->next=NULL;
  returnOK;
}

//入队
StatusEnQueue(LinkQueue&Q,ElemTypee){
  QueuePtrp=NULL;
  p=newQNode;
  if(!p)
    returnERROR;
  p->data=e;
  p->next=NULL;
  Q.rear->next=p;
  Q.rear=p;
  returnOK;
}

//出队
StatusDeQueue(LinkQueue&Q,ElemType&e){
  QueuePtrp=NULL;
  if(Q.front==Q.rear)
    returnERROR;
  p=Q.front->next;
  e=p->data;
  Q.front->next=p->next;
  if(Q.rear==p)      //注意当出队后为空队的情况
    Q.rear=Q.front;
  deletep;
  returnOK;
}

//判断是否为空队列
StatusQueueEmpty(LinkQueue&Q){
  returnQ.front==Q.rear?OK:ERROR;
}图结构：

//-----------------------图－多重表结构及函数--------------------------

//边结构
typedefstructEBox{
  intivex,jvex;
  structEBox*ilink,*jlink;
  intinfo;
}EBox;

//顶点结构
typedefstructVexBox{
  intdata;
  EBox*firstedge;
}VexBox;

//图结构
typedefstruct{
  VexBoxadjlist[MAX_VERTEX_NUM];
  intvexnum,edgenum;
}AMLGraph;

//建立图
voidcreateAMLGraph(AMLGraph&G,intvexnum,intedgenum,char*edges){
  intt,i,j;
  EBox*p;
  G.vexnum=vexnum;
  G.edgenum=edgenum;
  //initializtion
  for(t=0;t<G.vexnum;++t){
    G.adjlist[t].data=0;
    G.adjlist[t].firstedge=NULL;
  }
  //createedges
  for(t=0;t<G.edgenum;++t){
    i=int(*edges)-48;
    edges++;
    j=int(*edges)-48;
    edges++;
    p=newEBox;
    p->ivex=i;
    p->ilink=G.adjlist[i].firstedge;
    p->jvex=j;
    p->jlink=G.adjlist[j].firstedge;
    p->info=NULL;
    G.adjlist[i].firstedge=G.adjlist[j].firstedge=p;
  }
  
}

//打印出每个顶点的邻接顶点
voidPrintGraph(AMLGraphG){
  intt;
  EBox*p;
  cout<<"\nPrintAllvex-------------------------\n\n";
  for(t=0;t<G.vexnum;++t){
    cout<<t<<"--";
    p=G.adjlist[t].firstedge;
    if(p==NULL)cout<<"NULL";
    while(p!=NULL){
      if(t==p->ivex){
        cout<<p->jvex<<"";
        p=p->ilink;
      }else{
        cout<<p->ivex<<"";
        p=p->jlink;
      }
    }
    cout<<"\n";
  }
  cout<<"\nPrintAllvex-------------------------\n\n";
}

//返回图G中v顶点的第一个邻接顶点
intFirstAdjVex(AMLGraph&G,intv){
  if(G.adjlist[v].firstedge==NULL)
    return-1;
  if(v==G.adjlist[v].firstedge->ivex){
    returnG.adjlist[v].firstedge->jvex;
  }else{
    returnG.adjlist[v].firstedge->ivex;
  }
}

//返回图G中v顶点中邻接顶点w接下来的邻接顶点
intNextAdjVex(AMLGraph&G,intv,intw){
  EBox*p;
  p=G.adjlist[v].firstedge;
  while(p!=NULL){
    if(v==p->ivex){
      if(w==p->jvex){
        if(p->ilink==NULL)
          return-1;
        returnp->ilink->ivex==v?p->ilink->jvex:p->ilink->ivex;
      }else{
        p=p->ilink;
      }
    }else{
      if(w==p->ivex){
        if(p->jlink==NULL)
          return-1;
        returnp->jlink->ivex==v?p->jlink->jvex:p->jlink->ivex;
      }else{
        p=p->jlink;
      }
    }
  }
  return-1;
}深度广度遍历：

//-----------------------深度及广度优先遍历-------------------------

//对已经访问的顶点做标记
intvisited[MAX_VERTEX_NUM];

//深度优先遍历的递归函数DFS()
voidDFS(AMLGraph&G,intv){
  intw;
  cout<<v<<"->";
  visited[v]=TRUE;
  for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){
    if(visited[w]!=TRUE){
      DFS(G,w);
    }
  }
}

//深度优先遍历图
voidDFSTraverse(AMLGraph&G){
  inti;
  cout<<"\nDFSTraverse--------------------\n\n";
  for(i=0;i<G.vexnum;++i){
    visited[i]=FALSE;
  }
  for(i=0;i<G.vexnum;++i){
    if(!visited[i]){
      DFS(G,i);
      cout<<"NULL\n";
    }
  }
  cout<<"\nDFSTraverse--------------------\n\n";
}

//广度优先遍历图
voidBFSTraverse(AMLGraph&G){
  intv,w,i;
  LinkQueueQ;
  InitQueue(Q);
  cout<<"\nBFSTraverse--------------------\n\n";
  for(v=0;v<G.vexnum;++v){
    visited[v]=FALSE;
  }
  for(i=0;i<G.vexnum;++i){
    if(!visited[i]){
      visited[i]=TRUE;
      cout<<i<<"->";
      EnQueue(Q,i);
      while(!QueueEmpty(Q)){
        DeQueue(Q,v);
        for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){
          if(!visited[w]){
            visited[w]=TRUE;
            cout<<w<<"->";
            EnQueue(Q,w);
          }
        }
      }
      cout<<"NULL\n";
    }
  }
  cout<<"\nBFSTraverse--------------------\n\n";
}


voidmain(){
  AMLGraphG;
  char*edges;
  //输入边序列，每条边的两个顶点依次输入
  edges="98817565636051434230212010";
  //建立图，顶点数为10，边数为13，边序列为edges
  createAMLGraph(G,10,13,edges);
  PrintGraph(G);
  DFSTraverse(G);
  BFSTraverse(G);
}

TAG: