DFS(深度优先搜索 适合搜索全部解 在空间上有优势 因为不用保存搜索过程中的状态)
BFS（广度优先搜索 适合最优解 在空间上需要用一个队列来保存搜索过程）
一般情况下 DFS都是用递归来写算法 BFS需要手动维护一个队列queue
DFS代码-递归写法 模板（记住）
visited=set()
def dfs(node,visited):
visited.add(node)
#process current node here
…
for next_node in node.children():
if not next_node in visited:
dfs(next node,visited)
BFS代码模板
def BFS(Graph,start,end):
queue=[]
queue.append([start])
visited.add(start)
while queue:
node=queue.pop()
visited.add(node)
process(node)
nodes=generate_related_nodes(node)
queue.push(nodes)
#other processing work
…
二叉树的层次遍历（解法：BFS）
calss Sulotion{
public List<List> levelOrder(TreeNode root){
List<List> res=new ArrayList<List>();
if(root==nul) return res;
Queue q=new LinkedList<>(); 手动维护一个队列
q.add(root); 将初始节点加入队列
while(!q.isEmpty()){
int level_size=q.size(); 将泛型列队q的元素个数给这个level_size
List list=new List();
while(level_size>0){
TreeNode node=q.poll(); 将q初始化
list.add(node.val); list集合中加入q初始化的node的根节点
if(node.left!=null) q.add(node.left); 左节点
if(node.right!=null) q.add(node.right); 右节点
level_size–;
}
res.add(list);
}
return res;
}
}
岛屿数量（DFS）
class Solution{
int dx []=new {-1,1,0,0}; 定义sink方法里的k循环内的dx和dy
int dy []=new {0,0,1,-1};
char [] [] g;
public int numIslands(char [] [] gird){
g=gird; 设置全局变量
int islands=0;
for(int i=0;i<g.length;i++){ 遍历每一个点 是0还是1
for(int j=0;j<g[i].length;j++){
if(g[i][j]==‘0’]) continue; 0就是水 就过
islands+=sink(i,j); 否则就调用sink
}
return islands
}
}
private int sink(int i,int j){
if(g[i][j]==‘0’) return 0; 是0就返回水
g[i][j]=‘0’; 否则就让1变成0
for(k=0;i<dx.length;++k){ 1附近的1一个个遍历 都变成0
int x=i+dx[k]; int y=j+dy[k];
if(x>0&&x<g.length&&y>0&&y<g[i].length){ 在不超出边界的情况下
if(g[x][y]==‘0’) continue; 是0就跳过
sink(x,y); 否则接着调方法
}
}
return 1 返回陆地
}
}
