BFS DFS Code Template


BFS

Simple Version

int BFS(Node node, int start, int end){
    Queue<Node> queue;
  
  	q.add(start);
    visited.add(start)
    
    while(!q.isEmpty()){
      node = queue.pop();
      visited.add(node);
      
      process(node);
      nodes = generate_ralated_nodes(node);
      queue.push(nodes);
      
      // other process work
    }  
}

Detailed Version

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    // 核心数据结构
    Queue<Node> q; 
  	// 避免走回头路
    Set<Node> visited; 
    // 将起点加入队列
    q.offer(start); 
    visited.add(start);
    // 记录扩散的步数
    int step = 0; 

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}


For Example

public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> list = new ArrayList<>();
       if(root == null) return list;
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       queue.add(root);
       while(!queue.isEmpty()){
           int size = queue.size();
           List<Integer> sublist = new ArrayList<>();
           for(int i = 0; i< size; i++){
               TreeNode node = queue.poll();
               if(null != node){
                   sublist.add(node.val);
                   queue.add(node.left);
                   queue.add(node.right);
               }
           }
           if(!sublist.isEmpty()){
               list.add(sublist);
           }       
       }
       return list;
   }

DFS

visited = set()
boolean DFS(node, visited){
  visited.add(node);
  // process current node
  ...
  for next_node in node.children(){
    if(not next_node in visited){
      dfs(next_node, visited)
    }
      
  }   
}  

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

DFS非递归写法

boolean DFS(Node cur){
	 
}

Reference Link

五大算法代码模板（DFS 递归非递归都算上，是六个）