算法周刊 | Week10 深度优先搜索&广度优先搜索

vlambda
2022-02-10

算法周刊 | Week10 深度优先搜索&广度优先搜索

算法周刊

Week10

2021.9.25

1. 深度优先搜索介绍

图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。

它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然，深度优先搜索是一个递归的过程。

2. 深度优先搜索图解

2.1 无向图的深度优先搜

下面以"无向图"为例，来对深度优先搜索进行演示。

对上面的图G1进行深度优先遍历，从顶点A开始。

第1步：访问A。

第2步：访问(A的邻接点)C。在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。

第3步：访问(C的邻接点)B。在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。

第4步：访问(C的邻接点)D。在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。

第5步：访问(A的邻接点)F。前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。

第6步：访问(F的邻接点)G。

第7步：访问(G的邻接点)E。

因此访问顺序是：A -> C -> B -> D -> F -> G -> E

2.2 有向图的深度优先搜索

下面以"有向图"为例，来对深度优先搜索进行演示。

对上面的图G2进行深度优先遍历，从顶点A开始。

第1步：访问A。

第2步：访问B。在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。

第3步：访问C。在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。

第4步：访问E。接下来访问C的出边的另一个顶点，即顶点E。

第5步：访问D。接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。

第6步：访问F。接下应该回溯"访问A的出边的另一个顶点F"。

第7步：访问G。

因此访问顺序是：A -> B -> C -> E -> D -> F -> G

3.例题：洛谷的P1451求细胞数量

思路就是搞一个数组，不为0的地方就是细胞，然后dfs搜连通块，把搜到的都归0，保证不重复然后就是循环找没被归0的，答案+1。

#include <bits/stdc++.h>using namespace std;int n,m,ans,dx[]={-1,0,1,0},dy[]={0,-1,0,1},a[105][105];//a即地图，dx和dy方向增量数组就不用我讲了吧void dfs(int x,int y){    if (x>n||y>m||x<0||y<0)return;    a[x][y]=0;//标记为没有    for (int i=0;i<4;i++)if (a[x+dx[i]][y+dy[i]])dfs(x+dx[i],y+dy[i]);//如果有才搜}//搜索int main(){    scanf("%d%d",&n,&m);    for (int i=0;i<n;i++)    for (int j=0;j<m;j++)scanf("%1d",&a[i][j]);//只读1位    for (int i=0;i<n;i++)    for (int j=0;j<m;j++)if (a[i][j])ans++,dfs(i,j);//找    printf("%d",ans);//输出    return 0;}

4. 广度优先搜索介绍

广度优先搜索算法（Breadth-First Search，BFS）是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。

广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！

像这样的，求问从A到B的最短路径的结点数是多少？

5.基本思想和思路

1.根据路是不是相同的，我们可以创建一个布尔型二维数组way，way[w1][w2]=1代表从w1可以到达w2，=0时则代表不能, 设A的标志为0，其他的依次往后推。

Bool way[6][6]={ {0,0,1,1,1,0},{0,0,0,0,0,0},{0,1,0,0,0,0},{0,0,0,0,0,1},{0,0,0,0,0,1},{0,1,0,0,0,0}};

2.创建一个step数组，初始值为0，step[0]代表A的结点数，step[1]代表B的结点数，A有一结点所以开始假设step[0]=1，储存列出了几层子结点，也就是目前所有路径的结点数

创建一个队列，比如叫que（这里只是简单的设了个数组）

3.在队列que中加入A结点的标志0，步骤是将tail+=1并且que[tail]=0

然后搜索A的子结点，例如这样：

循环(i=0;i<=5;i++)//因为共有6个结点

如果(way[que[head+1]][i]==1)把子结点加入队列；

当循环完毕以后呢，就等于把A的子结点全找出来了，列出了一整层结点，删去第一个结点，step[2]和[3]和[4]都=step[0]+1，head-=1，那样head指的就是A的子结点C(标志2)了如图

4.继续判断，搜索2的子结点，并且加入队列，再删去2，搜索3的子结点……直到最后tail指针指的是B(标志1)，则输出step[1]（B的标志是1），就是最短路径数。如果head=tail了，说明队列为空，而且没找到答案，所以就没有可以到达目标结点的路，输出什么的就随你了。

#include <stdio.h>#include <string.h>Bool way[6][6]={{0,0,1,1,1,0},{0,0,0,0,0,0},{0,1,0,0,0,0},{0,0,0,0,0,1},{0,0,0,0,0,1},{0,1,0,0,0,0},};int main(){    int que[101],head=0,tail=1,i,step[6];    memset(step,0,sizeof(step));//初始化步数数组    que[1]=0;//初始化队首    step[0]=1; //结点A的步数为1    do    {        for(i=0;i<=5;i++)        {            if(way[que[head+1]][i]==1)            {                tail++;                que[tail]=i;                step[i]=step[que[head+1]]+1;                if(que[tail]==1)                {                    printf("%d",step[1]);                    return 0;                }            }        }        head++;    }while(head<tail);//当队列不为空    printf("no answer!");    return 0;}