dfs算法原理,dfs深搜

作为一种搜索算法，DFS对于寻找一个解的NP (包括NPC )问题起着很大的作用。但是，搜索算法毕竟时间复杂度是o(n )！的阶乘级算法效率非常低，当数据规模变大时，该算法将束手无策。节点v的所有边都被自己搜索到的情况下，搜索会追溯到发现节点v的边的开始节点。此过程将持续到找到所有可从源节点访问的节点为止。如果存在尚未发现的节点，则选择任一个作为源节点，重复上述过程，直到所有节点被访问为止。属于盲目搜索。

这些是百度上面的话，按照自己的理解，运用这个算法的时候要找一个头部节点，然后沿着这个头部节点一直找到最后满足条件的分节点，然后再找一条路径，沿着一条路走在不满足条件的时候自动上一层dfs算法通常与回溯算法一起使用。以下例子提到这些问题。每次解决这种类型的问题时，都要制定一个dfs扫描路线图，这有助于编写程序时的理性思考

这个问题是POJ上的1088

满意的面包我喜欢滑雪。因为滑雪真的很刺激。但是，为了获得速度，滑坡区域必须向下倾斜。然后，tldgs必须滑到斜坡的底部，再次走上坡，或者等待升降机载你一程。满意的面包想知道一个区域中最长的滑坡。区域由二维数组给出。数组中的每个数字表示点的高度。举个例子吧

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

可以从一点向上下左右相邻的4个点之一滑动，只有在高度变小的时候。在上例中，可滑行的滑坡为24-17-16-1。当然25-24-23--3-2-1更长。其实，这个是最长的。

输入

的第一行表示区域的行数r和列数c(1=r，C=100 )。下面是r行，每行有c个整数表示高度h，0=h=10000。

Output

输出最长区域的长度。

样品输入

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

样品输出

# include iostream # includecstdiousingnamespacestd； int R，c； int map[105][105]； int lqdrs[105][105]={ 0 }； intDFS(intI，int j ) { int k； if(LQDRS[I][j] ) return lqdrs[i][j]； if(I！=0map [ I-1 ] [ j ] map [ I ] [ j ] (k=DFS (I-1，j ) 1； if(kLQDRS[I][j] ) lqdrs[i][j]=k； (if ) I！=R - 1 map[i 1][j] map[i][j] ) k=DFS(I1，j ) 1； if(klqdrs[I][j] ) lqdrs[i][j]=k； (if ) j！=0map [ I ] [ j-1 ] map [ I ] [ j ] ((k=DFS (I，j-1 ) 1； if(klqdrs[I][j] ) lqdrs[i][j]=k； (if ) j！=C - 1 map[i][j 1]map[i][j] ) k=DFS(I，j 1 ) 1； if(klqdrs[I][j] ) lqdrs[i][j]=k； } return lqdrs[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(ksum ) sum=k； } } cout sum 1 endl；返回0； }该问题是从4个方向遍历各数1次，如果满足递减，则紧随dfs，不满足

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

再看下一个题，经典的八皇后问题，这个题用到了回溯加dfs，因为最后让输出八皇后排列的所有可能的情况

八皇后问题是一个以国际象棋为背景的问题：如何能够在 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. %dn", 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;}

最后在来一个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("%dn", dfs(0, 0));//输出结果}return 0;}

最后再说几句，这个dfs就是不撞南墙不回头那种，只要找不到就会一直找一下，另外觉得学习一下回溯算法会更好的运用dfs.（最近也是刚刚学习dfs，有不对的地方欢迎大家指出不足）