猫史档案馆

深度优先搜索

简介

深度优先搜索（Depth First Search,DFS）是一种搜索算法。

基本思想：

1.首先取一个初始元素。

2.寻找满足正在搜索的元素的条件的其他元素，并按特定的顺序逐个搜索这些元素。

3.如果搜索过程中找不到满足正在搜索的元素的条件的其他元素，则判断是否搜索成功，如果成功，做出相应操作并返回上一层；如果搜索不成功，则直接返回上一层。

4.每次搜索到一个元素，重复2和3两个步骤。

DFS通常使用递归函数，并配合栈来使用。

为了让大家能更好的理解，我讲的详细一点。

例子

深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索。例如图 1 是一个无向图，采用深度优先算法遍历这个图的过程为：

首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以，需要标记 V1 的状态为访问过；
然后遍历 V1 的邻接点，例如访问 V2 ，并做标记，然后访问 V2 的邻接点，例如 V4 （做标记），然后 V8 ，然后 V5 ；
当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ， V1 ；
通过查看 V1 ，找到一个未被访问过的顶点 V3 ，继续遍历，然后访问 V3 邻接点 V6 ，然后 V7 ；
由于 V7 没有未被访问的邻接点，所有回退到 V6 ，继续回退至 V3 ，最后到达 V1 ，发现没有未被访问的；
最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。

根据上边的过程，可以得到图 1 通过深度优先搜索获得的顶点的遍历次序为：

V1 -> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7

所谓深度优先搜索，是从图中的一个顶点出发，每次遍历当前访问顶点的临界点，一直到访问的顶点没有未被访问过的临界点为止。然后采用依次回退的方式，查看来的路上每一个顶点是否有其它未被访问的临界点。访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。

深度优先搜索是一个不断回溯的过程。

如果用C或C++来描述，其最简单的一类函数形式是：

int search(int k)
{
    for(i=1;i<=可能的位置;i++)
    if(满足条件)
    {
        保存结果
        if(到达目的)相应的操作
        else search(k+1);
        回溯
       }
}

例题讲解

素数环

题目描述：

从1到n(1<=n<=12）这n个数摆成一个环，要求相邻的两个数的和是一个素数。

输出格式：

请输出方案总数。如果无解，输出"no solution!"

题目分析

分析：

比如n=6。我们写一个环：

在1号放一个1。2号可以放2~6，放了2后，3号位置其中3和5满足条件。

先试探3。3号放了3以后，4好位置可以放4，但放了4之后，均不可行。故而3号放3不可行。

接下来试探3号位置放5，等等。

如此往复循环，直至所有可能性全部搜索完成。

思路：

b数组表示数字i有没有被用过。

a[i]表示放在环中的数字。

f函数的含义是判断素数。

Search中的k表示当前搜索的数。

核心代码：

int search(int k){
    int i;
    for(i=2;i<=n;i++){
        if(f(a[k-1],i)&&(!b[i])){
            a[k]=i;b[i]=1;//记录状态
            if(k==n){//到达目的
                if(f(a[n],a[1])) sum++;//如果成功，sum喵索下一个数
            }
            b[i]=0;回溯
        }
    }
}

Code：

//1.1素数环
#include<bits/stdc++.h>
using namespace std;
int a[100]={0};
bool b[100]={0},n;
int sum=0;
bool f(int a,int b){//这是个判断素数的函数
    int x=a+b;
    int i;
    if(c==2)return 1;
    for(i=2;i*i<=c;i++)if(c%i==0)return 0;//判断素数的核心代码
    return 1;
}
int search(int k){
    int i;
    for(i=2;i<=n;i++)//因为1已经用过了，从2开始搜索
    {
        if(f(a[k-1],i)&&(!b[i]))//如果前一个数和正在搜索的数的和是素数，并且这个数没有用过
        {
            a[k]=i;b[i]=1;//记录状态
            if(k==n)if(f(a[n],a[1]))sum++;//如果到达目的而且搜索成功
            else search(k+1); //如果没到达目的，那么继续下一层搜索
            b[i]=0;//k这个位置放上i，搜索完之后要回溯，因为已经把b[i]拿出那个环了
        }
    }
}
int main(){
    int i;
    cin>>n;
    a[1]=1;//第一个数是1
    search(2);//从第二个数开始搜索
    cout<<sum<<endl;
    return 0;
}

课后练习

跳马问题

题目描述：

马自左下角 (0,0)(0,0) 向右上角 (m,n)(m,n) 跳。规定只能往右跳，不准往左跳。

输入：

m和n。数据范围较小。

输出：

将路径总数打印出来。

思路提示

int n,m,ans=0,ax[4]={2,1,-1,-2},ay[4]={1,2,2,1};//表示4个方位，矩阵长宽，次数
void dfs(int x,int y){
    if(x==n&&y==m) ++ans;//到达目标点，次数+1
    if(x<0||x>n||y>m) return ;//如果越界，直接返回
    else for(int i=0;i<4;i++) dfs(x+ax[i],y+ay[i]);//不然继续搜索4个坐标
}

猫史档案馆

【C++基础算法】深度优先搜索（Depth First Search,DFS）

回复