数据结构-图的遍历

 2015/01/08   Share

1、相关原理

(1)深度优先搜索法﹕

深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：

　　Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
　　Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
　　void DFSTraverse (Graph G, Status(*Visit)(int v)){
　　VisitFunc = Visit;
　　for(v=0; v<G.vexnum; ++v)
　　visited[v] = FALSE; //访问标志数组初始化
　　for(v=0; v<G.vexnum; ++v)
　　if(!visited[v])
　　DFS(G, v); //对尚未访问的顶点调用DFS
　　}
　　void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G
　　visited[v]=TRUE; VisitFunc(v); //访问第v个顶点
　　for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
　　//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
　　//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
　　//若w是v的最后一个邻接点，则返回空（0）。
　　if(!visited[w])
　　DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS
　　}

(2)广度优先搜索法﹕

图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：

　　Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
　　Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
　　void BFSTraverse (Graph G, Status(*Visit)(int v)){
　　VisitFunc = Visit;
　　for(v=0; v<G.vexnum, ++v)
　　visited[v] = FALSE;
　　initQueue(Q); //置空辅助队列Q
　　for(v=0; v<G.vexnum; ++v)
　　if(!visited[v]){
　　visited[v]=TRUE; VisitFunc(v);
　　EnQueue(Q, v); //v入队列
　　while(!QueueEmpty(Q)){
　　DeQueue(Q, u); //队头元素出队并置为u
　　for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
　　if(!Visited[w]){ //w为u的尚未访问的邻接顶点
　　Visited[w]=TRUE; VisitFunc(w);
　　EnQueue(Q, w);
　　}
　　}
　　}
　　}

upload successful

2、详细设计

1.邻接表的存储表示

int visited[30];
# define MAX_VERTEX_NUM 30
# define OK 1
//typedef int VertexType;
typedef int InfoType;
//表节点
typedef struct ArcNode //弧
{
 int adjvex;
    struct ArcNode *nextarc;
}ArcNode;
//头节点
typedef struct VNode//表头
{
 int data;
    ArcNode *firstarc;//指向第一条依附该定点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];

2.图的构建

typedef struct//图
{  
 AdjList vertices;
    int vexnum,arcnum;//顶点数，弧数
    int kind;//图的种类标志
}ALGraph;
//邻接表存储表示
//图的创建
void CreateDG(ALGraph &G)
{  
 int k,i,v1;
    cout<<endl<<"请输入结点个数: ";
    cin>>G.vexnum;//节点数
 
    cout<<"请输入弧的个数: ";
    cin>>G.arcnum; //弧数

    for(i=1;i<=G.vexnum;i++)//初使化表头
    { 
  G.vertices[i].data=i; //初始化顶点值
     G.vertices[i].firstarc=NULL;//初始化指针
    }

   for(k=1;k<=G.vexnum;k++) //输入边
   { 
    
    int v2;
       cout<<"请输入与结点"<<k<<"相邻的边数:";
    cin>>v2;
    cout<<"请输入与第"<<k<<"个结点相连的结点编号: ";
    cin>>v1;
    ArcNode *p;
    p=(ArcNode*)malloc(sizeof(ArcNode));
    if(!p) exit(-1);
    p->adjvex=v1;
    p->nextarc=NULL;
    G.vertices[k].firstarc=p;

    

    for(int i=1;i<v2;i++)
    {
     int m;
     cout<<"请输入与第"<<k<<"个结点相连的结点编号: ";
           cin>>m;

           ArcNode *q;
           q=(ArcNode *)malloc(sizeof(ArcNode));//动态指针
           if(!q) exit(-1);

           q->adjvex=m;  //顶点给P
     q->nextarc=NULL;
           p->nextarc=q;
        p=q;
        //free(q);
    }
       //free(p);
   } 
}

3.深度优先遍历

void DFS (ALGraph G,int v )//深度搜索
{

 visited[v]=1;
 cout<<G.vertices[v].data<<"  ";
 ArcNode *x;
 x=(ArcNode*)malloc(sizeof(ArcNode));
 if(!x) exit(-1);
 x=G.vertices[v].firstarc;
 int w;
 for (;x;x=x->nextarc)
 {   w=x->adjvex;
  if(visited[w]==0)
   DFS(G,w);
 }
}

void DFSB (ALGraph G,int v)//深度搜索的边集
{

 visited[v]=1;
 ArcNode *y;
 y=(ArcNode*)malloc(sizeof(ArcNode));
 if(!y) exit(-1);
 y=G.vertices[v].firstarc;
 int u=G.vertices[v].data;
 int w;
 for(;y;y=y->nextarc)
 {   w=y->adjvex;
  if(visited[w]==0)
  {
   cout<<u<<"--->"<<w<<endl;
   DFSB(G,w);
  }
 }
}

typedef struct QNode
{
 int data;
 QNode *next;
}QNode,*QueuePtr;

typedef struct
{
 QueuePtr front;
 QueuePtr rear;
}LinkQueue;

4.广度优先遍历

void BFS(ALGraph G,int v)//广度搜索
{
 
 int u;
 LinkQueue Q;
 InitQueue(Q);
 if(visited[v]==0)
 {
  visited[v]=1;
  cout<<G.vertices[v].data<<"  ";
  EnQueue(Q,v);
  while(QueueEmpty(Q)!=1)
  {
   DeQueue(Q,u);
   ArcNode *z;
   z=(ArcNode*)malloc(sizeof(ArcNode));
      if(!z) exit(-1);
   z=G.vertices[u].firstarc;
   int w;
            for(;z;z=z->nextarc)
   {   w=z->adjvex;
    if(visited[w]==0)
    {
     visited[w]=1;
     cout<<w<<"  ";
     EnQueue(Q,w);
    }
   }
  }
 }
}

void BFSB (ALGraph G,int v)//广度搜索的边集
{
 
 int u;
 LinkQueue Q;
 InitQueue(Q);
 if(visited[v]==0)
 {
  visited[v]=1;
  EnQueue(Q,v);
  while(QueueEmpty(Q)!=1)
  {
   DeQueue(Q,u);
   ArcNode *r;
   r=(ArcNode*)malloc(sizeof(ArcNode));
   if(!r) exit(-1);
   r=G.vertices[u].firstarc;
   int w;
   for(;r!=NULL;r=r->nextarc)
   {   w=r->adjvex;
    if(visited[w]==0)
    {
     visited[w]=1;
     cout<<u<<"--->"<<w<<endl;
     EnQueue(Q,w);
    }
   }
  }
 }
}

5.主函数

int main()
{
 int i;
 ALGraph G;
    CreateDG(G);
 int x;
 cout<<"请输入结点数:";
 cin>>x;
 cout<<"邻接表为："<<endl;
 for(int j=1;j<=x;j++)
 {
  cout<<G.vertices[j].data<<"  ";
  ArcNode *p;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  if(!p) exit(-1);
  p=G.vertices[j].firstarc;
  while(p)
  {
   cout<<p->adjvex<<"  ";
   p=p->nextarc;
  }
  cout<<endl;
 }

 cout<<"请输入第一个要访问的结点序号："<<endl;
 int n;
 cin>>n;



 for( i=0;i<30;i++)
  visited[i]=0;
 cout<<"广度搜索："<<endl;
 BFS(G,n);

 for( i=0;i<30;i++)
  visited[i]=0;
 cout<<endl;
 cout<<"边集："<<endl;
 BFSB(G,n);

    for( i=0;i<30;i++)
  visited[i]=0;
 cout<<"深度搜索："<<endl;
 DFS(G,n);

    for( i=0;i<30;i++)
  visited[i]=0;
 cout<<endl;
 cout<<"边集："<<endl;
 DFSB(G,n);


 
    //system("pause");
 return 0;
}