算法：深度优先遍历和广度优先遍历

什么是深度、广度优先遍历深度优先遍历简称DFS（Depth First Search），广度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种方式。这两种遍历方式有什么不同呢？举个例子。我们来到一个游乐场，游乐场里有11个景点。我们从景点0开始，要玩遍游乐场的所有景点，可以有什么样的游玩次序呢？第一种是一头扎到底的玩法。我们选择一条支路，尽可能不断地深入

OceanStar的学习笔记

70919人浏览 · 2022-01-13 10:31:20

OceanStar的学习笔记 · 2022-01-13 10:31:20 发布

什么是深度、广度优先遍历

图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。

图的遍历过程中，根据搜索方法的不同，又可以划分为两种搜索策略：

深度优先搜索（DFS，Depth First Search）
广度优先搜索（BFS，Breadth First Search）

实现深度优先遍历的关键在于回溯，实现广度优先遍历的关键在于回放。

深度优先搜索

深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

那么，如何在图中应用深度优先搜索呢？

算法思想

对于图来说：
- 假设初始状态是图中所有顶点均未被访问
- 从某个顶点出发，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。
- 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实现深度优先遍历的关键在于回溯。所谓“回溯”，就是自后往前，追溯曾经走过的路径。

算法特点

深度优先搜索是一个递归的过程。
- 首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。
- 若不能继续前进，则回退一步再前进
- 若回退一步仍然不能前进，则连续回退至可以前进的位置为止。
- 重复此过程，直到所有与选定点相通的所有顶点都被遍历。
深度优先搜索是递归过程，带有回退操作，因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时，需要进行出栈操作，将当前位置回退至出栈元素位置。

图解过程

无向图的深度优先遍历

以下图所示无向图说明深度优先搜索遍历过程。

实例一

在这里插入图片描述
假设我们从顶点A开始，遍历过程中的每一步如下：

首先选取顶点A为起始点，输出A顶点信息，而且将A入栈，并且标记A为已访问顶点
A的邻接顶点有C、D、F，从中任意选取一个顶点前进。这里我们选取C为前进位置顶点。输出C顶点信息，将C入栈，并标记C为已访问顶点。当前位置指向顶点C
顶点C的邻接顶点有A、D、B，此时A已经标记为已访问顶点，因此不能继续访问。从B或者D中选取一个顶点前进，这里我们选取B顶点为前进位置顶点。输出B顶点信息，将B入栈，标记B顶点为已访问顶点。当前位置指向B
顶点B的邻接顶点只有C、E，C已被标记，不能继续访问，因此选取E为前进位置顶点，输出E顶点信息，将E入栈，标记E顶点，当前位置指向E。
顶点E的邻接顶点均已被标记，此时无法继续前进，则需要进行回退。将当前位置回退至顶点B，回退的同时将E出栈。
顶点B的邻接顶点也均被标记，需要继续回退，当前位置回退至C，回退同时将B出栈。
顶点C可以前进的顶点位置为D，则输出D顶点信息，将D入栈，并标记D顶点。当前位置指向顶点D。
顶点D没有前进的顶点位置，因此需要回退操作。将当前位置回退至顶点C，回退同时将D出栈。
顶点C没有前进的顶点位置，继续回退，将当前位置回退至顶点A，回退同时将C出栈。
顶点A前进的顶点位置为F，输出F顶点信息，将F入栈，并标记F。将当前位置指向顶点F。
顶点F的前进顶点位置为G，输出G顶点信息，将G入栈，并标记G。将当前位置指向顶点G。
顶点G没有前进顶点位置，回退至F。当前位置指向F，回退同时将G出栈。
顶点F没有前进顶点位置，回退至A，当前位置指向A，回退同时将F出栈。
顶点A没有前进顶点位置，继续回退，栈为空，则以A为起始的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
采用深度优先搜索遍历顺序为A->C->B->E->D->F->G。

利用一个临时栈来实现回溯，最终遍历完所有顶点

问题：

（1）必须选取A作为遍历的起点吗？

不是原则我们可以选取任何一个节点作为起点进行开始，进行深度优先遍历

（2）当有多个邻接点未被访问时，可以选取哪个作为下一个起点呢？

随便哪个都行。
当有多个临界点可选时，相当于走迷宫时出现了多个分叉路口，我们只要不走之前走过的路就行了。所以关键在于标记哪个点是否已经走过。不过，一般我们会定义一个原则，必须不碰重复点的情况下，选择走左/右手第一条没有走过的路，这样比较好理解

两个原则：

右手原则：在没有碰到重复顶点的情况下，分叉路口始终是向右手边走，每路过一个顶点就做一个记号
左手原则：在没有碰到重复顶点的情况下，分叉路口始终是向左手边走，每路过一个顶点就做一个记号

下面以右手原则进行深度优先遍历再看个例子

实例二

在这里插入图片描述

原则我们可以选取任何一个节点作为起点进行开始，进行深度优先遍历，假设我们从顶点A开始，遍历过程中的每一步如下：

第一步：从顶点A开始，将顶点A标记为已访问节点
第二步：根据右手原则，访问顶点B，并将B标记为已访问节点
第三步：右手原则，访问顶点C
第四步：右手原则，访问顶点D
第五步：右手原则，访问顶点E
第六步：右手原则，访问顶点F
第七步：右手原则，应该先访问顶点F的邻接顶点A，但发现A已经被访问，则访问A之外的最右侧顶点G
第八步：右手原则，先访问顶点B，顶点B已经被访问；在访问顶点D，顶点D已经被访问；最后访问顶点H
第九步：发现顶点H的邻接顶点均已被访问，则退回到顶点G;
第十步：顶点G的邻接顶点均已被访问，则退回到顶点F；
第十一步：顶点F的邻接顶点已被访问，则退回到顶点E；
第十二步：顶点E的邻接顶点均已被访问，则退回到顶点D；
第十三步：顶点D的邻接顶点I尚未被访问，则访问顶点I；
第十四步：顶点I的邻接顶点均已被访问，则退回到顶点D;
第十五步：顶点D的邻接顶点均已被访问，退回到顶点C；
第十六步：顶点C的邻接顶点均已被访问，则退回到顶点B；
顶点B的邻接顶点均已被访问，则退回到顶点A，顶点A为起始顶点，深度优先搜索结束。

图的深度优先搜索和二叉树的前序遍历、中序遍历、后序遍历本质上均属于一类方法。

上面的过程可以总结为以下3个步骤：

首先选定一个未被访问过的顶点V作为起始顶点（或者访问指定的起始顶点V），并将其标记为已访问
然后搜索与顶点V邻接的所有顶点，判断这些顶点是否被访问过，如果有未被访问过的顶点W；再选取与顶点W邻接的未被访问过的一个顶点并进行访问，依次重复进行。当一个顶点的所有的邻接顶点都被访问过时，则依次回退到最近被访问的顶点。若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取出一个并重复上述过程，直到与起始顶点V相邻接的所有顶点都被访问过为止。
若此时图中依然有顶点未被访问，则再选取其中一个顶点作为起始顶点并进行遍历，转（2）。反之，则遍历结束。

有向图深度优先搜索

在这里插入图片描述
（1）以顶点A为起始点，输出A，将A入栈，并标记A为已经访问。当前位置指向A。

（2）以A为尾的边只有1条，且边的头为顶点B，则前进位置为顶点B，输出B，将B入栈，标记B。当前位置指向B。

（3）顶点B可以前进的位置有C与F，选取F为前进位置，输出F，将F入栈，并标记F。当前位置指向F。

（4）顶点F的前进位置为G，输出G，将G入栈，并标记G。当前位置指向G。

（5）顶点G没有可以前进的位置，则回退至F，将G出栈。当前位置指向F。

（6）顶点F没有可以前进的位置，继续回退至B，将F出栈。当前位置指向B。

（7）顶点B可以前进位置为C和E，选取E，输出E，将E入栈，并标记E。当前位置指向E。

（8）顶点E的前进位置为D，输出D，将D入栈，并标记D。当前位置指向D。

（9）顶点D的前进位置为C，输出C，将C入栈，并标记C。当前位置指向C。

（10）顶点C没有前进位置，进行回退至D，回退同时将C出栈。

（11）继续执行此过程，直至栈为空，以A为起始点的遍历过程结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

性能分析

当图采用邻接矩阵存储时，由于矩阵元素个数为 $n^2$ ，因此时间复杂度就是 $O(n^2)$

当图采用邻接表存储时，邻接表中只是存储了边结点(e条边，无向图也只是2e个结点)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)。

广度优先搜索

算法思想

思想：
- 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点
- 然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
- 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实现广度优先遍历的关键在于回放。

回溯与重放是完全相反的过程。

仍然以刚才的图为例，按照广度优先遍历的思想

我们先遍历顶点0，然后遍历其邻接点1、3
接下来我们要遍历更外围的顶点，可是如何找到这些更外围的顶点呢？我们需要把刚才遍历过的顶点1,3按照顺序回顾一遍，从顶点1发现了邻接点2，从顶点3发现了邻接点4。于是得到了顺序2,4
再把刚才遍历过的顶点2，4按照顺序回顾一遍，分别得到邻接点5，6
再把刚才遍历过的顶点5，7按照顺序回顾一遍，分别得到邻接点7，7。7只需要打印一次，所以我们需要一个东西来标记当前顶点是否已经访问过

在这里插入图片描述

像这样把遍历过的顶点按照之前的遍历顺序重新回顾，就叫做重放。

同样的，要实现重放也需要额外的存储空间，可以利用队列的先入先出特性来实现。
另外，还需要标记某个点是否已经被访问过，可以用数组、set等来实现

可以看出，广度优先搜索它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

算法特点

广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。

图解过程

无向图的广度优先搜索

在这里插入图片描述

（1）选取A为起始点，输出A，A入队列，标记A，当前位置指向A。

在这里插入图片描述

（2）队列头为A，A出队列。A的邻接顶点有B、E，输出B和E，并将B和E入队，以及标记B、E为已访问。当前位置指向B。
在这里插入图片描述
（3）队列头为B，B出队列。B的邻接顶点有C、D，输出C、D，将C、D入队列，并标记C、D。当前位置指向B。

在这里插入图片描述

（4）队列头为E，E出队列。E的邻接顶点有D、F，但是D已经被标记，因此输出F，将F入队列，并标记F。当前位置指向E。

在这里插入图片描述
（5）队列头为C，C出队列。C的邻接顶点有B、D，但B、D均被标记。无元素入队列。当前位置指向C。

在这里插入图片描述
（6）队列头为D，D出队列。D的邻接顶点有B、C、E，但是B、C、E均被标记，无元素入队列。当前位置指向D。

（7）队列头为F，F出队列。F的邻接顶点有G、H，输出G、H，将G、H入队列，并标记G、H。当前位置指向F。
在这里插入图片描述
（8）队列头为G，G出队列。G的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向G。

（9）队列头为H，H出队列。H的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向H。

（10）队列空，则以A为起始点的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

有向图的广度优先搜索

在这里插入图片描述
（1）选取A为起始点，输出A，将A入队列，标记A。

在这里插入图片描述
（2）队列头为A，A出队列。以A为尾的边有两条，对应的头分别为B、C，则A的邻接顶点有B、C。输出B、C，将B、C入队列，并标记B、C。

在这里插入图片描述

（3）队列头为B，B出队列。B的邻接顶点为C，C已经被标记，因此无新元素入队列。

在这里插入图片描述
（4）队列头为C，C出队列。C的邻接顶点有E、F。输出E、F，将E、F入队列，并标记E、F。

在这里插入图片描述
（5）列头为E，E出队列。E的邻接顶点有G、H。输出G、H，将G、H入队列，并标记G、H。

在这里插入图片描述
（6）队列头为F，F出队列。F无邻接顶点

在这里插入图片描述

（7）队列头为G，G出队列。G无邻接顶点

在这里插入图片描述
（8）队列头为H，H出队列。H邻接顶点为E，但是E已被标记，无新元素入队列

在这里插入图片描述
（9）队列为空，以A为起始点的遍历过程结束，此时图中仍有D未被访问，则以D为起始点继续遍历。选取D为起始点，输出D，将D入队列，标记D

在这里插入图片描述
（10）队列头为D，D出队列，D的邻接顶点为B，B已被标记，无新元素入队列

在这里插入图片描述
（11）队列为空，且所有元素均被访问，广度优先搜索遍历过程结束。广度优先搜索的输出序列为：A->B–>C->E->F->G->H->D。

算法分析

我们来看下，广度优先搜索的时间、空间复杂度是多少呢？假设图有V个顶点，E条边

每个顶点都需要进出一遍队列，每个边都会被访问一次。所以，广度优先搜索的时间复杂度是O(V+E)。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)
广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列上。这两个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。

总结

图的遍历主要就是这两种遍历思想，深度优先搜索使用递归方式，需要栈结构辅助实现。广度优先搜索需要使用队列结构辅助实现。在遍历过程中可以看出，

对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点
对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。

实现

深度优先遍历

当图采用邻接矩阵进行存储，递归的实现操作：

#define MAXVBA 100
#define INFINITY 65536

typedef struct {
    char vexs[MAXVBA];
    int arc[MAXVBA][MAXVBA];
    int numVertexes, numEdges;
} MGraph;

// 邻接矩阵的深度有限递归算法

#define TRUE 1
#define FALSE 0
#define MAX 256

typedef int Boolean; // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAX]; // 访问标志的数组

void DFS(MGraph G, int i){
    visited[i] = TRUE;
    printf("%c", G.vexs[i]);

    for (int j = 0; j < G.numVertexes; ++j) {
        if (G.arc[i][j] == 1 && !visited[j]){
            DFS(G, j); // 对为访问的邻接顶点递归调用
        }
    }
}


// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
    int i;

    // 初始化所有顶点状态都是未访问过状态
    for (i = 0; i < G.numVertexes; ++i) {
        visited[i] = FALSE;
    }

    //防止图为非联通的情况，遍历整个图
    for (i = 0; i < G.numVertexes; ++i) {
        if (!visited[i]){   // 若是连通图，只会执行一次
            DFS(G, i);
        }
    }
}

当图采用邻接矩阵进行存储，栈的实现操作：

void DFS_Stack(MGraph G, int i)
{
  int node;
  int count = 1;
  printf("%c ", G.vexs[i]); // 打印已访问顶点
  visited[i] = TRUE;
  node = i;
  push(i); //开始的节点入栈
  while(count < G.numVertexes) //still has node not visited
  {
  /* 所有被访问的节点依次入栈，只有node当找不到下一个相连的节点时，才使用出栈节点 */
    for(j=0; j < G.numVertexes; j++)
    {
      if(G.arc[node][j] == 1 && visited[j] == FALSE)
      {
        visited[j] = TRUE;
        printf("%c ", G.vexs[j]);
        count++;
        push(j); //push node j
        break;
      }
    }
    if(j == G.numVertexes) //与node相连的顶点均已被访问过，所以需要从stack里取出node的上一个顶点，再看该顶点的邻接顶点是否未被访问
      node = pop();
    else      //找到与node相连并且未被访问的顶点，
      node = j;
  }
}

请添加图片描述
邻接表存储下图的深度优先搜索代码实现，与邻接矩阵的思想相同，只是实现略有不同：

// 邻接表的深度有限递归算法

#define TRUE 1
#define FALSE 0
#define MAX 256

typedef int Boolean; // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAX]; // 访问标志的数组

void DFS(GraphAdjList 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);
    }
  }
}

广度优先遍历

请添加图片描述

// 邻接矩阵的广度遍历算法
void BFSTraverse(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] )
    {
      printf("%c ", G.vex[i]);
      visited[i] = TRUE;
      EnQueue(&Q, i);
      
      while( !QueueEmpty(Q) )
      {
        DeQueue(&Q, &i);
        for( j=0; j < G.numVertexes; j++ )
        {
          if( G.art[i][j]==1 && !visited[j] )
          {
            printf("%c ", G.vex[j]);
            visited[j] = TRUE;
            EnQueue(&Q, j);
          }
        }
      }
    }
  }
}