BFS算法详解

一、概述

  作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率非常低，在数据规模变大时，这种算法就显得力不从心了。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

  这些是百度上面的一些话，根据自己理解，就是说这个算法运用的时候就是找一个头结点，然后沿着这个头结点一直找下去，直到走到最后一个满足条件的分节点，然后再寻找另一条路径，当沿着一条路走不满足条件时会自动的跳入上一层节点进行判断。
  dfs算法通常与回溯算法一起使用，下面的例子中将会提到这些问题。每次做这种类型的题可以先画出dfs遍历的路径图，这样有利于写程序时的合理思维

二、实例讲解

2.1、例题1

Description
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25

 #include<iostream>  
    #include<cstdio>  
    using namespace std;  

    int R, C;  
    int map[105][105];  
    int mark[105][105] = { 0 };  


    int dfs(int i, int j)  
    {  
    int k;  
    if (mark[i][j]) return mark[i][j];  
    if (i != 0 && map[i - 1][j] < map[i][j])  
    {  
    k = dfs(i - 1, j) + 1;  
    if (k> mark[i][j]) mark[i][j] = k;  
    }  
    if (i != R - 1 && map[i + 1][j] < map[i][j])  
    {  
    k = dfs(i + 1, j) + 1;  
    if (k>mark[i][j]) mark[i][j] = k;  
    }  
    if (j != 0 && map[i][j - 1]<map[i][j])  
    {  
    k = dfs(i, j - 1) + 1;  
    if (k>mark[i][j]) mark[i][j] = k;  
    }  
    if (j != C - 1 && map[i][j + 1]<map[i][j])  
    {  
    k = dfs(i, j + 1) + 1;  
    if (k>mark[i][j]) mark[i][j] = k;  
    }  
    return mark[i][j];  

    }  

    int main()  
    {  
    int i, j, k, sum = 0;  
    scanf("%d%d", &R, &C);  
    for (i = 0; i < R; i++)  
    {  
    for (j = 0; j < C; j++)  
    {  
    scanf("%d", &map[i][j]);  
    }  
    }  
    for (i = 0; i < R; i++)  
    {  
    for (j = 0; j < C; j++)  
    {  
    k = dfs(i, j);  
    if (k>sum) sum = k;  
    }  
    }  
    cout << sum + 1 << endl;  
    return 0;  
    }  

解析：这个题就是把每个数从四个方向都遍历一次，如果满足递减的话就接着dfs，不满足时候把这个数存起来
这个题有几个注意的问题，就是第一个要考虑好边缘临界点，就是四周的点不可以进行某些方向的移动，其次还有一点特别要注意，dfs中的if (mark[i][j]) return mark[i][j];这句话就是为了重复计算，假如从24开始的话已经算出来23，然后如果从25开始，遇到24的话直接可以找到23，而不用在遍历一次，节省了时间。

2.2、实例2

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。


Input
无输入。

Output
按给定顺序和格式输出所有八皇后问题的解（见Sample Output）。

Sample Input

Sample Output

No. 1
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
No. 2
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
No. 3
1 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
No. 4
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
No. 5
0 0 0 0 0 1 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
No. 6
0 0 0 1 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 7
0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 8
0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
No. 9
0 0 0 0 1 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 0 
...以下省略

解析：这个就是定义hang 【num】和列i，然后每一行从第一个位置开始放皇后，如果可以的话就标记为1，然后接着往下找第二行，也是从第二行第一个位置开始找，满足接着第三行。当如果发现第三行不能再放置皇后了，这个时候第三行那个位置已经标记为1 ，所以这个时候就回溯到第二行也就是上一层从新判断同时把标记为1 的变量还原为0，直到满足条件输出。题中有一个陷阱，深搜的时候是按列输出的，不是行输出。

  #include<iostream>  
    #include<cstdio>  
    #include<cstdlib>  
    using namespace std;  
    int hang[11], n=8;  
    int a[10][10] = { 0 };  
    int t = 1;  
    void print()  
    {  
        printf("No. %d\n", t++);  
        for (int i = 1; i <= 8; i++)  
        {  
            for (int j = 1; j <= 8; j++)  
            {  
                printf("%d ", a[j][i]);  
            }  
            printf("\n");  
        }  
    }  
    bool judge(int num)  
    {  
        for (int i = 1; i < num; i++)  
            if (hang[num] == hang[i] || abs(hang[i] - hang[num]) == num - i)  
                //判断列和对角线  
                return 0;  
        return 1;  
    }  

    void dfs(int num)  
    {  
        if (num >= 9){  
            print();  
        }  
        for (int i = 1; i <= 8; i++)  
        {  
            hang[num] = i;  
            if (a[num][i]!=1&&judge(num))  
            {  
                a[num][i] = 1;  
                dfs(num + 1);  
                a[num][i] = 0;  
            }  

        }  

    }  

    int main()  
    {  
        //freopen("1.txt", "w", stdout);  
            dfs(1);  
        return 0;  
    }  

2.3、实例3

最后在来一个dfs解决迷宫问题，就是1代表障碍，0代表通过，然后问从头到尾一共有几条路径可以走到终点，这个问题同样是dfs加回溯，就是遍历每一个走过点的上下左右四个方向，直到最后走到终点再重新回溯就是return 1，把走过的还原为0,（因为走过的路都标记为1），最后return sum把顺带可以return的结果输出。

  /* 
      输入两个数n，m，代表迷宫的行和列 
      接下来输入n行m列由0,1组成的迷宫，其中1代表障碍 
      求从左上角到右下角的路线个数 
    */  
    #include<stdio.h>  
    #define N 1000//最大行列数  
    int mg[N][N];//存放迷宫图  
    int re[N][N];//记录之前是否走过  
    int n, m;//行，列  
    int dfs(int x, int y){//现在在(x,y)点  
        if(x < 0 || x > n - 1 || y < 0 || y > m - 1 || re[x][y] == 1 || mg[x][y] == 1) return 0;//走出界外或之前走过或遇到障碍  
        if(x == n - 1 && y == m - 1) return 1;//走到终点  
        re[x][y] = 1;//该点标记为走过  
        int sum = 0;  
        sum += dfs(x - 1, y);//向左走  
        sum += dfs(x + 1, y);//向右走  
        sum += dfs(x, y - 1);//向上走  
        sum += dfs(x, y + 1);//向下走  
        re[x][y] = 0;//该点还原为没有走过  
        return sum;  
    }  
    int main(){  
        int i, j;  
        while(~scanf("%d%d", &n, &m)){//输入行列  
            for(i = 0; i < n; i ++)  
            {  
                for(j = 0; j < m; j ++) scanf("%d", &mg[i][j]);//读入迷宫图  
            }  
            printf("%d\n", dfs(0, 0));//输出结果  
        }  
        return 0;  
    }  

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>