天津网址:深度优先搜索原理与实践(java)

admin 4个月前 (05-14) 科技 44 1

概论

深度优先搜索属于图算法的一种,是一个针对图和树的遍历算法,英文缩写为 DFS 即 Depth First Search。深度优先搜索是图论中的经典算法,行使深度优先搜索算法可以发生目标图的响应拓扑排序表,行使拓扑排序表可以利便的解决许多相关的图论问题,如最大路径问题等等。一样平常用堆数据结构来辅助实现 DFS 算法。其历程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能接见一次。

基本步奏

(1)对于下面的树而言,DFS 方式首先从根节点1最先,其搜索节点顺序是 1,2,3,4,5,6,7,8(假定左分枝和右分枝中优先选择左分枝)。

   

(2)从 stack 中接见栈顶的点;

   

(3)找出与此点毗邻的且尚未遍历的点,举行符号,然后放入 stack 中,依次举行;

   

(4)若是此点没有尚未遍历的毗邻点,则将此点从 stack 中弹出,再凭据(3)依次举行;

  天津网址:深度优先搜索原理与实践(java) 第1张  

 

(5) 由于与节点 5 相连的的节点都被接见过了,于是5被弹出,查找与 4 相邻但没有被接见过的节点:

  天津网址:深度优先搜索原理与实践(java) 第2张  

(6)直到遍历完整个树,stack 里的元素都将弹出,最后栈为空,DFS 遍历完成。

  天津网址:深度优先搜索原理与实践(java) 第3张 (7) 天津网址:深度优先搜索原理与实践(java) 第4张 针对上面的历程,可以用代码示意如下:
 // 用于纪录某个节点是否接见过
   private
Map<String, Boolean> status = new HashMap<String, Boolean>();
  // 用于保留接见历程中的节点
private Stack<String> stack = new Stack<String>();
  // 入口,这里选择 1 为入口
public void DFSSearch(String startPoint) { stack.push(startPoint); status.put(startPoint, true); dfsLoop(); } private void dfsLoop() {
     // 到达终点,竣事循环
if(stack.empty()){ return; } // 查看栈顶元素,但并不出栈 String stackTopPoint = stack.peek(); // 找出与此点毗邻的且尚未遍历的点,举行符号,然后所有放入list中。 List<String> neighborPoints = graph.get(stackTopPoint); for (String point : neighborPoints) { if (!status.getOrDefault(point, false)) { //未被遍历 stack.push(point);
          // 加上已接见符号 status.put(point,
true); dfsLoop(); } }
     // 若是毗邻点都被接见了,那么就弹出,相当于是恢复操作,也就是在递归后面做的。 String popPoint
= stack.pop(); System.out.println(popPoint); }

通过上面的示例,基本领会 dfs 使用。

通用框架

其一样平常框架原理如下:

void dfs()
{
    if(到达终点状态)
    {
        ... //凭据题意添加 
        return; 
    }
    if(越界或不正当状态) return; 
    if(特殊状态) // 剪枝
         return;
    for(扩展方式)
    {
        if(扩张方式所到达状态正当)
        {
            修改操作; // 凭据题意添加
            符号;
            dfs();
            (还原符号);
            //是否加上还原符号凭据题意
            //若是加上还原符号就是回溯法 
        }
    }
}

通过这个 dfs 框架可以看出该方式主要有以下几个纪律:

  1. 接见路径的确定。凭据差别的问题思索怎么才算是一条接见路径,若何去实现遍历。

  2. 起点条件。从哪个点最先接见?是否每个点都需要看成起点?第一次 dfs 挪用至关重要。

  3. 递归参数。也就是 dfs 递归怎么在上一个节点的基础上继续递归,实现递归依赖什么参数?需要知道一条路径上各个节点之间的关系,当前接见节点。

  4. 终结条件。接见的终结条件是什么?好比到达界限点,所有点已经都接见过了。终结条件需要在下一次递归前举行判断。

  5. 接见标志。当一条路走不通的时刻,会返回上一个节点,实验另一个节点。为了制止重复接见,需要对已经接见过的节点加上符号,制止重复接见。

  6. 剪枝。属于算法优化。好比已经知道沿着当前路径再走下去也不会知足条件的时刻,提前终止递归。

下面将连系几道算法题来加深对深度优先搜索算法的明白。

1、全排列

问题:给定大于0的数字n,输出数字 1 ~ n 之间的全排列。

对于这道问题,有些人可能会好奇为啥这到问题可以使用 dfs 算法。对于全排列,实在可以通过树的形式来举行明白:

天津网址:深度优先搜索原理与实践(java) 第5张

 可以发现就是一个 n 叉树,总共是 n 层,下面接纳前面总结的纪律来看看算法实现原理:

  1. 接见路径:从起始位置到叶节点就是一个排列,也就是一条路径

  2. 起点条件:start 下面有 n 个节点,每个点都可以被看成起始点,说明需要接纳 for 循环方式,。

  3. 递归参数:当前接见的节点位置,定位下一个递归节点。需要一个变量纪录数字的排列,需要输出。节点总数 n,便于知道何时递归竣事。

  4. 终结条件:递归接见到节点数到达 n 层的时刻住手递归。

  5. 接见标志:不需要,可重复接见;

  6. 剪枝:不需要,没有其他需要提前终止递归的条件。

下面就是算法实现:

     // 挪用入口,起始点
   dfs(total, 0, "");
   // 递归参数:tatal 示意数字n, index 当前接见节点,s 纪录排列方式
public void dfs(int total, int index, String s) {
     // 终结条件
if (index == total) { System.out.println(s); return; }
     // 对于每个节点,当前有 total 种选择
for (int i= 1;i<=total;i++) { dfs(total, index+1, s+i); } }

可以发现,代码照样很简单的。

 

695. 岛屿的最大面积

给定一个包罗了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 组成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直偏向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)笼罩着。

找到给定的二维数组中最大的岛屿面积。(若是没有岛屿,则返回面积为 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注重谜底不应该是 11 ,由于岛屿只能包罗水平或垂直的四个偏向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注重: 给定的矩阵grid 的长度和宽度都不跨越 50。

 对于这道问题照样接纳之前的剖析方式:

  1. 接见路径:节点中相邻的1组成一条路径。0 直接无视。

  2. 起点条件:二维数组的每个点都可以看成起点。以是两个 for 循环来举行挪用。

  3. 递归参数:当前接见的节点位置(x,y),二维数组表,从表中查找下一个节点

  4. 终结条件:到达二维数组的界限,节点为0

  5. 接见标志:需要,不能重复接见;可以将接见过的节点置为0,制止再次接见,重复盘算。

  6. 剪枝:只有在节点即是1的时刻,才挪用dfs。这样可以削减挪用次数。

问题解答如下:

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length <1 || grid[0].length<1) {
            return 0;
        }
        int rx = grid.length;
        int cy = grid[0].length;
        int max = 0;
        for (int x =0; x< rx; x++) {
            for (int y= 0;y<cy; y++) {
                if (grid[x][y]==1) { //只有节点即是1才挪用,这里就可以算作是剪枝,算法的优化 int num = dfs(grid,x,y);
                   max = Math.max(max, num);
                }
            }
        }
        return max;

    }
   // 递归参数:节点位置x,y, 二维数组 private int  dfs (int[][] grid, int x, int y){
        int rx = grid.length;
        int cy = grid[0].length;
     // 界限条件,节点为0
if (x >= rx || x < 0 || y>=cy || y<0 || grid[x][y]==0 ) { return 0; }
     // 直接修改原数组来符号已接见 grid[x][y]
=0;
     // 每次递归就示意面积多了一块
int num = 1;
     // 每个节点有四种差别的选择偏向 num
+= dfs(grid, x-1, y); num += dfs(grid, x, y-1); num += dfs(grid, x+1, y); num += dfs(grid, x, y+1); return num; } }

200. 岛屿数目

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你盘算网格中岛屿的数目。

岛屿总是被水笼罩,而且每座岛屿只能由水平偏向或竖直偏向上相邻的陆地毗邻形成。

此外,你可以假设该网格的四条边均被水笼罩。

示例 1:

// 输入:
11110
11010
11000
00000
// 输出: 1

示例 2:

// 输入:
11000
11000
00100
00011
// 输出: 3

注释: 每座岛屿只能由水平和/或竖直偏向上相邻的陆地毗邻而成。

可以发现,这道问题与前面的问题很类似,关于 dfs 规则这里就不在剖析了,留给人人自己去剖析。

问题解答如下:

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length < 1 || grid[0].length<1) {
            return 0;
        }
        int num = 0;
        int rx = grid.length;
        int cy = grid[0].length;
     // 起始点
for (int x =0;x<rx;x++) { for (int y =0;y<cy;y++) {
          // 问题要求,'0'不符合路径条件
if (grid[x][y]=='1') { dfs(grid,x,y); num++; } } } return num; }    // 递归条件 private void dfs(char[][] grid, int x, int y) { int rx = grid.length; int cy = grid[0].length;
     // 终结条件
if (x<0 || x>=rx || y<0 || y>= cy || grid[x][y] == '0') { return; }
     // 接见偏向实质是由接见路径来决议的,就是你得想清晰怎么才算一条路径 grid[x][y]
='0'; dfs(grid,x-1,y); dfs(grid,x,y-1); dfs(grid,x+1,y); dfs(grid,x,y+1); return ; } }

到这里,深度优先搜索的理论和实践就讲完了,信赖看到这里的小伙伴应该也掌握了其算法的原理,以及若何去誊写。

 

参考文章 

基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

,

菲律宾申慱手机登录网址

欢迎进入菲律宾申慱手机登录网址!Sunbet 申博提供申博开户(sunbet开户)、SunbetAPP下载、Sunbet客户端下载、Sunbet代理合作等业务。

皇冠APP声明:该文看法仅代表作者自己,与本平台无关。转载请注明:天津网址:深度优先搜索原理与实践(java)

网友评论

  • (*)

最新评论

  • 新皇冠会员登录 2020-05-14 01:58:17 回复

    www.66rfd.com(www.lphggs.com)是Sunbet 申博的官方网站。www.66rfd.com提供申博开户(sunbet开户)、SunbetAPP下载、Sunbet代理合作等业务。文笔太好了吧。

    1

站点信息

  • 文章总数:539
  • 页面总数:0
  • 分类总数:8
  • 标签总数:985
  • 评论总数:166
  • 浏览总数:2702