leetcode之BFS与DFS

发表于 | 更新于 | 评论数： | 阅读次数：

简介

深度优先与广度优先算法，从名字上便很好理解，以在二叉树结构中搜索某一值为例：

  1. 深度优先算法将从顶点V开始，沿着一个路径一直走到底（叶子节点），如果搜索到目标值则退出，否则返回上一个还有子节点未被搜索的节点继续搜索。
  2. 广度优先算法将从顶点V开始，依次访问当前节点未被访问过的子节点，再从子节出发，继续访问他们的子节点，直到所有节点被访问。（相当于树的层次遍历）
  3. 一般说来，能用DFS解决的问题都能用BFS解决。DFS通过递归实现，易于实现，DFS的常数时间开销会比较少，所以大多数情况下优先考虑DFS实现。然后就是，DFS容易栈溢出，而BFS可以自己控制队列的长度。

BFS

基本实现思想：

​ （1）顶点v入队列。

​ （2）当队列非空时则继续执行，否则算法结束。

​ （3）出队列取得队头顶点v；

​ （4）查找顶点v的所以子节点，并依次进入队列；

​ （5）转到步骤（2）。

树的层次遍历

  • 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
  • 这里使用2个数组保存节点，也可以使用queue这一数据结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<int> print_vec;
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<TreeNode*> node_pre,node; //使用2个数组，分别保存上一层的树节点与当前层的树节点
        if(root==NULL)return print_vec;
        if(root->left!=NULL)
            node.push_back(root->left);
        if(root->right!=NULL)
            node.push_back(root->right);
        print_vec.push_back(root->val);
        while(!node.empty())
        {
            for(auto i=0;i<node.size();i++)
            {
                print_vec.push_back(node[i]->val);
            }
            vector<TreeNode*> x;
            node_pre.swap(node);
            x.swap(node);
            for (auto i=0;i<node_pre.size();i++)
            {
                //遍历node_pre的节点，并将子节点保存到node
                if(node_pre[i]->left!=NULL)
                    node.push_back(node_pre[i]->left);
                if(node_pre[i]->right!=NULL)
                    node.push_back(node_pre[i]->right);
            }
        }
        return print_vec;
    }
};

DFS　

递归实现：

​ （1）访问顶点v，打印节点；

​ （2）遍历v的子节点w，while（w存在），递归执行该节点；

非递归实现：

​ （1）访问顶点v，顶点v入栈S，打印输出顶点，visited[v]=1

​ （2）while(栈S非空)

​ x=栈S的顶元素(不出栈)；

​ if(存在并找到未被访问的x的子结点w)

​ 　　访问w，打印输出，visited[w]=1；w进栈;

​ else

​ 　　x出栈;

注：visited[x]=1，标记该节点已被访问

二叉树的深度

  • 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(!pRoot)
            return 0;
        else{
            return max(!(pRoot->left)?1:TreeDepth(pRoot->left)+1,!(pRoot->right)?1:TreeDepth(pRoot->right)+1);
        }
    }
};

二叉树中和为某一值的路径

  • 输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > res;
        vector<int> n;
        if(!root) return res;
        finder(root,expectNumber,res,n);
        return res;
    }
    void finder(TreeNode* root,int expectNumber,vector<vector<int> > &res,vector<int> &n){
        if(!root||root->val>expectNumber||(root->val==expectNumber&&(root->left||root->right))) return;
        else if(root->val==expectNumber&&(!root->left&&!root->right)){
            n.push_back(root->val);
            res.push_back(n);
            n.pop_back();
            return;
        }
        n.push_back(root->val);
        finder(root->left,expectNumber-root->val,res,n);
        finder(root->right,expectNumber-root->val,res,n);
        n.pop_back();
    }
};

迷宫寻路问题

推箱子

  • 这是网易的一道笔试题，需要将箱子推到指定位置。输入一张地图，其中*表示箱子,X表示人,@表示目的地,#表示障碍。
  • 这道题采用广度优先算法，第一次将箱子推送到目标地即为最短路径。使用st[x][y][bx][by]（人位 置(x,y),箱子位置(bx,by) ）记录状态，防止重复的路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<vector>
#include<queue>
using std::cin ;
using std::cout;
using std::vector;
using std::endl;
using std::queue;
/*
4 4
....
..*@
....
.X..
*/
int st[10][10][10][10];
int x,y,bx,by,tx,ty;
 int m ,  n ;
vector<vector<char>> mm ;
bool valid(int x,int y ){
  //判断移动是否合法
   if(x>=0&&x<m&&y>=0&&y<n&&mm[x][y]!='#')return true;
   return false;
}
int main(){
   cin >> m >>n;
   mm= vector<vector<char>>(m , vector<char>(n ,' ' ));
   for(int i =0 ; i < m ; i++)
     for(int j=0 ; j< n ; j++)
    {
        char t ;
        cin >>t;
        if(t=='X'){
          x = i;y = j;
         // cout <<x<<" "<<y<<endl;
        }
        if(t == '*'){
           bx = i ;by = j;
         }
        if(t == '@'){
          tx = i ; ty = j;
        }
        mm[i][j] = t;           
    } 
//  record every state of the 
  vector<vector<int>> next= {{-1, 0},{1,0},{0,1},{0,-1}};
  queue<vector<int>> que ;
  que.push({x,y,bx,by});
  st[x][y][bx][by] =1 ;//状态初始化
  while(!que.empty())
  {
      vector<int> t = que.front();
      que.pop();
      x =  t[0];  y = t[1];  bx=t[2]; by = t[3];
      for(int i =0 ; i < next.size() ; i++)
      {
         int nx = x+next[i][0],ny =y+next[i][1]; 
         int nnx = nx+next[i][0],nny =ny+next[i][1]; 
         if(valid(nx,ny)&&(nx!=bx||ny!=by)&&st[nx][ny][bx][by]==0)
         //移动合法且状态不重复且不退箱子的情况下
         {
             st[nx][ny][bx][by]= st[x][y][bx][by]+1;
             que.push({nx,ny,bx,by});
             continue;
         }else if(nx==bx&&ny==by&&valid(nnx,nny)&&st[nx][ny][nnx][nny]==0){ 
         //移动合法且状态不重复且推箱子情况
              st[nx][ny][nnx][nny] = st[x][y][bx][by]+1;
              if(mm[nnx][nny]=='@'){cout<<st[nx][ny][nnx][nny]-1;return 0;}
              que.push({nx,ny,nnx,nny});
          }
      }
  } 
   cout <<-1;
   return 0;
}

迷宫寻路

  • 请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
链接：https://www.nowcoder.com/questionTerminal/e3fc4f8094964a589735d640424b6a47
来源：牛客网
//AC代码:
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
using namespace std;
char G[105][105];
int book[105][105][1200],N,M;
int Next[4][2]={0,1,0,-1,1,0,-1,0};
int bfs(int,int);
struct node{
    int x,y,k,step;
    node(int x,int y,int k,int step):x(x),y(y),k(k),step(step){}
};
int main(){
    int i,j;
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&N,&M)!=EOF){
        for(i=0;i<N;i++) scanf("%s",G[i]);
        memset(book,0,sizeof(book));
        int flag=0;
        for(i=0;i<N;i++){
            if(flag==1) break;
            for(j=0;j<M;j++)
                if(G[i][j]=='2'){
                    flag=1;
                    book[i][j][0]=1;
                    printf("%d\n",bfs(i,j));
                    break;
                }
        }
    }
}
int bfs(int startX,int startY){
    queue<node> Q;
    Q.push(node(startX,startY,0,0));
    while(!Q.empty()){
        node head=Q.front();Q.pop();
        if(G[head.x][head.y]=='3') return head.step;
        for(int i=0;i<4;i++){
            int nx=head.x+Next[i][0],ny=head.y+Next[i][1];
            if(nx>=N||nx<0||ny>=M||ny<0||G[nx][ny]=='0') continue;
            int key=head.k;
            if('a'<=G[nx][ny]&&G[nx][ny]<='z') key=key|(1<<(G[nx][ny]-'a'));
            if('A'<=G[nx][ny]&&G[nx][ny]<='Z'&&(key&(1<<(G[nx][ny]-'A')))==0) continue;
            if(!book[nx][ny][key]){
                book[nx][ny][key]=1;
                Q.push(node(nx,ny,key,head.step+1));
            }
        }
    }
    return 0;
}//这题就是普通的bfs多了‘钥匙’这个状态
 //所以book[x][y][key]的意义就是 横坐标为x,纵坐标为y,钥匙状态为key的点是否访问过
 //钥匙的状态 就用二进制数表示 最多10 把钥匙 那就是1024
 //比如我现在有第二把钥匙和第四把钥匙  那么我的钥匙状态就是 0101000000 也就是 320

参考资料

  1. https://www.cnblogs.com/skywang12345/p/3711483.html

本文标题:leetcode之BFS与DFS

文章作者:微石

发布时间:2018年08月04日 - 09:08

最后更新:2018年08月20日 - 18:08

原始链接:akihoo.github.io/posts/cdd358bc.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。