Bread First Search
Use Case
从图上某个点出发，找到其他所有点（整个图）
- Traversal in Graph
- Level Order Traversal
- 层级遍历需要提前取size
- Connected Component
- 引入HashMap，因为可能存在环
- Topological Sorting
- Level Order Traversal
- Shortest Path in Simple Graph
- 简单图求最短路径（即图中每条边长度都是1，且没有方向）
Summary
- 复杂度O(n) （n个节点）或者O(m) (m条边)，每个点只过一次
- 空间复杂度O(n)
Template
using Queue
需要分层的情况，多一个for循环，同时要记得提前取size
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList result = new ArrayList(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { ArrayList<Integer> level = new ArrayList<Integer>(); //get the size first since size is changing int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode head = queue.poll(); level.add(head.val); // null check if (head.left != null) queue.offer(head.left); if (head.right != null) queue.offer(head.right); } result.add(level); } return result; }