数据结构与算法18-图的遍历

81 阅读 0 评论 54 点赞

我是靠谱客的博主沉默网络，最近开发中收集的这篇文章主要介绍数据结构与算法18-图的遍历，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

从图中某一个顶点出发访遍图中其余顶点，且使每个顶点权被访问一次，这一过程就叫做图的遍历（Traversing Graph）。

深度优先遍历（Depth_First_Search）

从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径想通的顶点都被访问到。

事实上，我们这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都补充访问到为止。

如果我们用的是邻接矩阵方式，则代码如下：

typedef  int  Boolean;

Boolean  visited[MAX];

/*邻接矩阵的深度优先递归算法*/

void   DFS(MGraph  G,int i)

{

       int   j;

       visited[i] = TRUE;

       printf(“%c”,G.vexs[i]);

       for(j=0;j<G.numVertexes;j++)

            if(G.arc[i][j]==1 && !visited[j]) DFS(G,j);  //对访问的邻接顶点递归调用。

}



/*邻接矩阵的深度遍历操作*/

void  DFSTravese(MGraph   G)

{

    int  i;

    for(i=0;i<G.numVertexes;i++)

          visited[i]=FALSE;  //初始化访问状态为未访问

     for(i=0;i<G.numVertexes;i++)

          if(!visited[!])

                DFS(G,i);

}

如果结构图是邻接表结构，其DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成链表而不同

代码如下：

/*邻接链表的深度优先递归算法*/

void  DFS(GrapAdjList  GL,int  i)

{

        EdgeNode   *p;

         visited[i] = true;

         printf(“%c”,GL->adjList[i].data); //打印顶点

         p=GL->adjList[i].firstedge;

         while(p)

         {

                if(!visited[p->adjvex])

                      DFS(GL,p-adjvex);

                 p=p->next;

         }

}



/*邻接表的深度遍历操作*/

void  DFSTraverse(GraphAdjList   GL)

{

       int  i;

      for(i=0;i<GL->numVertexes;i++)

                    visited[i] = FALSE;

          for(i=0;i<GL->numVertexes;i++)

           if(!visited[i])

                 DFS(GL,i);

}

对比丙从此不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的怕有元素，因此需要O(n2)的时间。而邻接表做的存储结构时，找邻接点的所需的时间取决于顶点和边的数量，所以是O（n+e）显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

对于有向图而非言，由于它只是对通道存在可行或不可行，算法上没有变化，是完全可以通用的。

广度优先遍历

又称为广度优先搜索，简称BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历类似于树的层序遍历。

如图的图稍微变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与BF有边的顶点C、I、G、E为第三层，再将这四个顶点的边的D、H放在第四层

邻接矩阵的广度优先遍历算法

void    SFSTraverse(MGraph    G)

{

         int   i,j;

         Queue   Q;

         for(i=0;i<G.numVertexes;i++)

                visited[i] = FALSE;

         InitQueue(&Q);

         for(i=0;i<G.numVertexes;i++) //对第一个顶点做循环

         {

               if(!visited[i])

                {

                       visited[i] = TRUE;

                       printf(“%c”,G.vexs[i]);    //打印顶点，也可以其他操作

                       EnQueue(&Q,&i);                   //将此顶点入队列

                        while(!QueueEmpty(Q))

                        {

                             //队列不为空

                             DeQueue(&Q,&i);   //待队中元素出队，赋值给i

                            for(j=0;j<G.numVertexes;j++)

                           {   //判断其它顶点和当前顶点存在边且未访问过

                                   if(G.arc[i][j]==1 &&!visited[j])

                                     {

                                            visited[j] = TRUE;

                                             printf(“%c”,G.vexs[j]);

                                             EnQueue(&Q,j);    //将找到的此顶点入队列

                                          }

                             }

                         }

                   }

}

邻接表的广度遍历算法

void  BFSTraverse(GraphAdjList    GL)

{

          int   i;

          EdgeNode   *p;

          Queue    Q;

          for(i=0;i<GL->numVertexes;i++)

                visited[i] = FALSE;

           InitQueue(&Q);

          for(i=0;i<GL->numVertexes;i++)

          {

                   if(!visited[i])

                     {

                           visited[i]=TRUE;

                            printf(“%c”,GL->adjList[i].data);

                            EnQueue(&Q,i);

                            while(!QueueEmpty(Q))

                            {

                                 DeQueue(&Q,&i);

                                p=GL->adjList[i].firstedge; //找到当前顶点边表链表头指针

                                 while(p)

                                  {

                                          if(!visited[p->adjvex])

                                          {

                                              visited[p->adjvex] = TRUE;

                                              printf(“%c”,GL->adjList[p->adjvex].data);

                                               EnQueue(&Q,p->adjvex);

                                           }

                                            p =p->next;

                                   }

                            }

                      }

           }

}

对比的图的深度优先遍历与广度优先遍历算法，你会发现，它们在时间复杂度上是一样的，不同之处仅仅在对于顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的，只是视不同的情况选择不同的算法。