dfs函数python,DFS实现

Python算法-深度优先搜索&广度优先搜索（DFS&BFS）

大树满足条件的和 等于 每个子树满足条件的数的和之和

result = 0 + 10 + 15 + 18

深度优先搜索必然会使用到 递归

必须使用到辅助队列，用于判断

找到共同的祖先

对相同像素的相邻位置进行渲染

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

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

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

相关问答

Q1: dfs(0,0,b)是什么意思？

dfs是深度优先搜索的意思。

这一句应该是dfs算法代码中的一句，意思是调用名为dfs的函数，传入三个参数，分别为0,0，b

前两个参数0,0可能是坐标，后面一个参数是根据实际问题有着具体的含义。

比如“水管工游戏”，其中设置int变量front表示进水口方向，然后dfs函数为：

void dfs(int x,int y,int front)

{

//判断是否越界

......

//判断这个管道是否在路径中已经使用过

......

//当前水管是直管的情况

......

//进水口在左边的情况

//进水口在上边的情况

//进水口在右边的情况

//进水口在下边的情况

......

//当前水管是弯管的情况

......

//进水口在左边的情况

//进水口在上边的情况

//进水口在右边的情况

//进水口在下边的情况

......

}

Q2: 如何理解这个代码。跪求大神分步解释！！

main函数很容易理解，就先不说了。讲一下dfs()吧

dfs()是一个简单的递归函数，和其他递归函数一样，它将一直递进执行到出现确切的数值后，再逐步回归到最外层。

来说一下每行代码的实际作用

int dfs(int n,int k)

{

int num; //声明变量，注意各个变量的作用域仅仅是当前这一层

//在以后调用的每个dfs都会声明属于它自己的num变量

if(n==k) //简单的逻辑判断，检查传给当前这一层函数的两个参数是否相同

{ //相同的话返回k

return k;

}

num=dfs(n-n/k,k); //调用一个新的dfs，并且当这个dfs有返回值的时候赋值给当前的num参数

return ((num-1)/(k-1)+num); //计算(当前的num-1)/(k-1)+当前的num)，并将结果返 回给调用它的函数

}

楼主，最直观的办法就是你手动模拟一遍，自己设置n和k两个参数，再手动模拟运行dfs，你会恍然大悟的。