前言

生若夏花，死如秋叶

本小节知识目录

1. 深度遍历算法原理及图解
2. 深度遍历算法例题应用
   1：全排列问题
   2：ABC+DEF=GHI问题
   3：二维数组寻找点到点的最短路径
   4：求岛屿的面积
   5：求岛屿的个数
   6：地板的埔法有多少种
   7：二叉树的深度遍历
   8：图的深度遍历
   9：图的最短路径求解
   10：找子集等于某给定的数

正题开始

1：深度遍历算法原理及图解

• 1：深度遍历算法理论

深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

• 2：深度遍历算法图解
  1：需要遍历的图
  
  讯享网1:从A点出发，红色代表A点被访问。
  2:有A->B,A->C都可行，都可以遍历，这里我选择遍历C。
  3：再遍历C之后，也可遍历C->B,C->D 我这里选择遍历C->D。
  4：现在由D->E 这里遍历了E。
  5：E已经不可以再遍历了。然后返回D,D又不可以遍历B，放回C，然后C->B可以。所以从C->B 就实现遍历。
  

总结

这就是整个深度遍历的全过程。

1：例题讲解

• 全排列问题

#include<iostream> using namespace std; //交换两个数 void swap(int &a, int &b) { 
    int temp; temp = a; a = b; b = temp; } void dfs(int list[], int k, int m) { 
    if (k == m) { 
    for (int i = 0; i <= m; i++) cout << list[i]; cout << endl; } for (int i = k; i <= m; i++) { 
    swap(list[i], list[k]); dfs(list, k + 1, m); swap(list[i], list[k]); } } int main(void) { 
    int a[] = { 
    1, 2, 3 }; int m = 2; dfs(a, 0, 2); system("pause"); } 

思路和总结

也就是深度遍历的思想，首先我们去第一个，然后访问下一个，然后再接下来一个。图解

• 2：ABC+DEF=GHI 问题

题目描述
从1~9中选择出3组数组，组成一个百位数，每个数只能使用一次，譬如
718+245=963

讯享网#include<iostream> using namespace std; //交换两个数 void swap(int &a, int &b) { 
    int temp; temp = a; a = b; b = temp; } void dfs(int list[], int k, int m) { 
    if (k == m) { 
    int X1 = list[0] * 100 + list[1] * 10 + list[2]; int X2 = list[3] * 100 + list[4] * 10 + list[5]; int X3 = list[6] * 100 + list[7] * 10 + list[8]; if (X1 + X2 == X3) cout << X1 << "+" << X2 << "=" << X3 << endl; return; } for (int i = k; i <= m; i++) { 
    swap(list[i], list[k]); dfs(list, k + 1, m); swap(list[i], list[k]); } return; } int main(void) { 
    int a[] = { 
    1, 2, 3,4,5,6,7,8,9 }; int m = 2; dfs(a, 0, 8); system("pause"); } 

总结思路

也就是全排序的过程，然后再调用全排序数字的位置，进行判断，就可以找出这样的ABC+DEF = GHI

• 3：二维数组寻找最短路径问题

0代表可以走。代表不可以走，选择从（1,1）~（3,3）的最短路径

#include<iostream> using namespace std; //ABC + DEF = GHI问题 bool visited[5][5] = { 
    false }; int step = 1; int minstep = 999; int map[5][5] = { 
    { 
   1,1,1,1,1}, { 
   1,0,0,1,0}, { 
   1,0,1,0,1}, { 
   1,0,0,0,1}, { 
   1,0,0,0,0} }; void dfs(int x, int y,int step) { 
    if (x > 4 || x<1 || y>4 || y<1 || visited[x][y] == true) return; if (x == 3 && y == 3) { 
    if (minstep > step) minstep = step; //打印出步长 cout << step << endl; } else { 
    if (visited[x][y] == false && (map[x][y] == 0)) { 
    visited[x][y] = true; dfs(x + 1, y, step + 1); dfs(x - 1, y, step + 1); dfs(x, y + 1, step + 1); dfs(x, y - 1, step + 1); visited[x][y] = false; } return; } } int main(void) { 
    dfs( 1, 1,0); cout << minstep << endl; system("pause"); } 

总结

本题的解决方式也就是深度遍历算法，也就是一直查找到底。也就是深度遍历算法的应用。

• 4：求岛屿的面积

题目描述
给一个二维数组，0代表湖泊，1代表陆地，每个1代表1m^2 求给定的二维数组中某个位置所在岛屿的面积。例题
0 0 0 0
0 1 1 0
0 1 0 0
0 0 0 0 求位置（1,1）所在岛屿的面积 如图所示为3 m^2;