数据结构与算法—图的遍历

图的遍历

在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到。
我们可以设置一个全局型标志数组visited来标志某个顶点是否被访问过，未访问的值为0，访问过的值为1。
图的遍历有两种方法： 深度优先搜索遍历（DFS ）、 广度优先搜索遍历（BFS） 。

深度优先搜索

深度优先搜索思想

首先访问顶点i，并将其访问标记置为访问过，即visited[i] =1；
然后搜索与顶点 i 有边相连的下一个顶点 j ，若j未被访问过，则访问它，并将j的访问标记置为访问过，visited[j]=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；
若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完为止。

例如：

对下图所示无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。

1, 2, 4, 8, 5, 6, 3, 7

1, 2, 5, 8, 4, 7, 3, 6

1, 3, 6, 8, 7, 4, 2, 5

可以看出，从某一个顶点出发的遍历结果是不唯一的。但是,若我们给定图的存贮结构,则从某一顶点出发的遍历结果应是唯一的。

1. 用邻接矩阵实现图的深度优先搜索

    #define MAX_VERTEX_NUM 100
    typedef int VertexType; /*假设图中结点的数据类型为整型*/
    typedef struct  {
       VertexType v[MAX_VERTEX_NUM];     /*顶点表*/
       int A[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   /*邻接矩阵*/
       int vexnum,arcnum; /*图的顶点数和弧数*/
    }MGraph;
    int visited[MAX_VERTEX_NUM];
    void DFSM(MGraph G, int i)
    {  
       printf("%5d",G.v[i]); /*访问顶点i*/
       visited[i]=1;                 /*标记顶点i已访问*/
       for(int j=0;j<G.vexnum;j++) {
          if (!visited[j] && G.A[i][j]==1) 
             DFSM(G,j); /*若某个邻接顶点尚未访问，则递归访问它*/
       }
    }

用上述算法和无向图G7，可以描述从顶点1出发的深度优先搜索遍历过程，其中实线表示下一层递归调用，虚线表示递归调用的返回。可以得到从顶点1的遍历结果为 1, 2, 4, 8, 5, 6, 3, 7。同样可以分析出从其它顶点出发的遍历结果。

2. 用邻接表实现图的深度优先搜索

图的邻接表存储结构定义：

    typedef struct ArcNode {  
      int    adjvex;  /*该弧所指向的顶点的位置*/
      struct ArcNode  *nextarc; /*下一条弧*/
      InfoType   info;   /*该弧上的权值*/
    } ArcNode;
    typedef int VertexType; 
    typedef struct VNode { 
        VertexType  data;   
        ArcNode  *firstarc; 
    }VNode;
    typedef struct {  
         VNode  vertices[MAXV];
         int   vexnum, arcnum; 
    } ALGraph;

邻接表存储时的深度优先搜索算法：

    int visited[MAX_VERTEX_NUM];
    void DFS(ALGraph G, int v)
    { 
       ArcNode *p;
       printf("%5d",G.vertices[v].data); /*访问顶点v*/
       visited[v]=1;              /*标记顶点v已访问*/
       p=G.vertices[v].firstarc;  /*取第一个邻接边*/
       while (p) {
       if (!visited[p->adjvex]) 
          DFS(G,p->adjvex); /*递归访问*/
          p=p->nextarc;  /*找顶点v的下一个邻接点*/
       }
    }

用刚才算法，可以描述从顶点7出发的深度优先搜索遍历示意图，其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。遍历序列为 7， 3， 1， 2， 4， 8， 5， 6。

广度优先搜索

广度优先搜索的思想

借助队列先进先出的特点实现

首先访问顶点i，并将其访问标志置为已被访问，即visited[i]=1；
接着依次访问与顶点i有边相连的所有顶点W1，W2，…，Wt；
然后再按顺序访问与W1，W2，…，Wt有边相连又未曾访问过的顶点；
依此类推，直到图中所有顶点都被访问完为止。

在无向图G7中，从顶点1出发的广度优先搜索遍历序列举三种为：

1, 2, 3, 4, 5, 6, 7, 8

1, 3, 2, 7, 6, 5, 4, 8

1, 2, 3, 5, 4, 7, 6, 8

1. 用邻接矩阵实现图的广度优先搜索遍历

根据该算法用及图7-14中的邻接矩阵，可以得到图G7的广度优先搜索序列，

若从顶点1 出发，广度优先搜索序列为：1，2，3， 4，5， 6，7，8。

若从顶点3出发，广度优先搜索序列为：3， 1， 6， 7， 2， 8， 4， 5。

邻接矩阵存储时的宽度优先搜索算法：

    void BFSM(MGraph G,int i)  
    {
        int j;
        Queue Q;  InitQueue(&Q); 
        InQueue(&Q,i);
        printf("%5d",G.v[i]);  /*访问初始顶点v*/
        visited[i]=1;                  /*置已访问标记*/
        while(OutQueue(&Q,&i)) 
        {    /*若队列不空时循环*/
            for(j=0;j<G.vexnum;j++) 
            {
                if (!visited[j] && G.A[i][j]==1) 
                {
                    visited[j]=1;
                    printf("%5d",G.v[j]); /*访问v*/
                    InQueue(&Q,j);     /*该顶点进队*/
                }
            }
        }
    }

2. 用邻接表实现图的广序优先搜索遍历

可以得到图G7的广度优先搜索序列，

若从顶点1出发，广度优先搜索序列为：1，2，3，4，5，6，7，8，

若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2。

邻接表存储时的宽度优先搜索算法：

    void BFS(ALGraph G,int v)  
    { 
        ArcNode *p; int x;
        Queue Q;  InitQueue(&Q); InQueue(&Q,v);
        printf("%5d",G.vertices[v].data);  /*访问初始顶点v*/
        visited[v]=1;        /*置已访问标记*/
        while(OutQueue(&Q,&x)) 
        {       /*若队列不空时循环*/
            
            p=G.vertices[x].firstarc;   /*与x邻接的第一个顶点*/
            while(p!=NULL) 
            {
                if (visited[p->adjvex]==0) 
                {   /*若未被访问*/ 
                    visited[p->adjvex]=1;
                    printf("%5d",G.vertices[p->adjvex].data); 
                    InQueue(&Q,p->adjvex);     /*该顶点进队*/
                }
                p=p->nextarc;            /*找下一个邻接点*/
            } 
        }
    }

Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。

它的内容包括：

大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：

想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询

同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】即可免费领取。

阅读全文