一定要早日上岸鸭 · July 28, 2021 0

BFS && DFS 模板:

广度优先搜索BFS:

def bfs(seed): q = queue() q.put(seed) while not q.empty(): now = q.get() for 所有和 now 相邻的节点 x: q.put(x)

深度优先搜索DFS:

def dfs(seed): if 递归出口(seed): return for 所有相邻节点x: dfs(x)

BFS: Java 双端队列的实现:

class Solution { ArrayDeque<TreeNode> dq = new ArrayDeque<TreeNode>(); List<List<Integer>> ret = new ArrayList<List<Integer>>(); public void bfs(TreeNode root){ if(root==null) return; dq.addLast(root); while(!dq.isEmpty()){ int size = dq.size(); List<Integer> nodes = new ArrayList<Integer>(); while(size>0){ TreeNode res = dq.pollFirst(); nodes.add(res.val); if(res.left!=null) dq.addLast(res.left); if(res.right!=null) dq.addLast(res.right); size--; } ret.add(nodes); } } public List<List<Integer>> levelOrder(TreeNode root) { bfs(root); return ret; } }

BFS: 九章的实现方式

public class BFSSample { public static void main(String[] args) { Queue<Node> queue = new ArrayDeque<>(); HashMap<Node, Integer> distance = new HashMap<Node, Integer>(); // distance 用来记录七点到节点距离,并且可以判断是否访问过 // 放入初识节点到queue中: queue.offer(node); distance.put(node, 0); // 访问队列 // while循环和每次都pop出来一个点: while(!queue.isEmpty()) { Node node = queue.poll(); for (Node neighbor : node.getNeighbors()) { if (distance.containsKey(neighbor)) { // 邻居已经visit过不要再visit continue; } distance.put(neighbor, distance.get(node) + 1); queue.offer(neighbor); } } } }