ZXAlgorithm - C4 BFS

Outline
BFS in Binary tree
BFS in Graph
BFS on Matrix
Topological Sorting

0 什么时候使用BFS

图的遍历，最短路径，非递归找所有方案

1 BFS in Binary tree

• What
  Hashmap(Xml,json)
  Thrift(facebook)
  Protobuf(google)
• Consideration
  Readability
  Compress rate
• How
  BFS better for you to draw the whole tree
  1 Process:
  Add all nodes()
  Remove nulls from the back
  Prints all stuff
• Level order traversal
  Leetcode 102.Binary Level order traversal
  https://leetcode.com/problems/binary-tree-level-order-traversal/
  http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal/
  使用队列作为数据结构；分层用两个queue
• Serialization: XML，Json，Thrift，ProtoBuf
  持久化和网络传输时，需要序列化
  考虑压缩率和可读性
  Leetcode 297.Binary Tree Serialization
  http://www.jiuzhang.com/solutions/binary-tree-serialization/
  https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
• Related Problems
  Leetcode 107.Binary Tree Level Order Traversal II
  http://www.lintcode.com/en/problem/binary-tree-level-order-traversal-ii/ http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal-ii/
  https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
  Leetcode 103.Binary Tree Zigzag Order Traversal
  http://www.lintcode.com/en/problem/binary-tree-zigzag-level-order-traversal/ http://www.jiuzhang.com/solutions/binary-tree-zigzag-level-order-traversal/
  https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
  Leetcode 114.Convert Binary Tree to Linked Lists by Depth
  http://www.lintcode.com/en/problem/convert-binary-tree-to-linked-lists-by-depth/ http://www.jiuzhang.com/solutions/convert-binary-tree-to-linked-lists-by-depth/
  https://leetcode.com/problems/flatten-binary-tree-to-linked-list

2 BFS in Graph

• Difference: have cycle
  Use Hashmap to record whether it has been walked through
  Java: HashMap / HashSet
  C++: unordered_map / unordered_set
  Python: dict / set
• Example:
  Leetcode 133.Clone graph
  https://leetcode.com/problems/clone-graph/
  https://www.jiuzhang.com/solution/clone-graph/
  https://leetcode.com/problemset/all/?search=clone%20graph
  https://blog.csdn.net/zdavb/article/details/47667989
  时间复杂度O(N+M)N为点数，M为边数
  Initial:
  Map<Node,Node> map.put(node, new Node); List<Node> queue.add(node)
  Process:
  One point to find all points
  Clone point
  Clone edges
  Use hashmap to connect the vertices and edges
  Return:
  map.get(node)
  Leetcode 127.Word Ladder
  使用defaultdict存一个d*g ->['dog','dig','dfg']来获取下一个单词
  https://leetcode.com/problems/word-ladder/
  https://leetcode.com/problems/word-ladder/solution/
  http://www.jiuzhang.com/solution/word-ladder/
• Related question:
  Leetcode 261.Graph valid tree
  http://www.lintcode.com/problem/graph-valid-tree/
  https://www.jiuzhang.com/solution/graph-valid-tree/
  N > V; All connected
  Initial:
  Map<Integer, Set<Integer>> graph = initialGraph; List<Integer> queue.add(0); Set<Integer> hash.add(0)
  Process:
  Use bfs: use queue and hashset to add all connected nodes
  Return:
  check the size of set if it equals hash.size();
  Lintcode Search graph nodes
  http://www.lintcode.com/problem/search-graph-nodes/
  https://www.jiuzhang.com/solution/search-graph-nodes/
  Initial:
  BFS: within the for loop check whether it have passed the node(use hashset) to decide if add to queue
  Leetcode 323.Number of Connected Components in an Undirected Graph
  https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph
  http://www.lintcode.com/problem/connected-component-in-undirected-graph/
  https://www.jiuzhang.com/solution/number-of-connected-components-in-an-undirected-graph/
  Leetcode 444.Sequence reconstruction
  http://www.lintcode.com/problem/sequence-reconstruction/
  https://leetcode.com/problems/sequence-reconstruction
  https://www.jiuzhang.com/solution/sequence-reconstruction/

3 BFS in Matrix

矩阵和图的对比：

• Leetcode 200.Number of Islands
  https://leetcode.com/problems/number-of-islands/
  http://www.lintcode.com/problem/number-of-islands/
  https://www.jiuzhang.com/solution/number-of-islands/
  Initial:
  Int islands
  Progress:
  Traverse the whole matrix
  For each island found exclude adjacent nodes by bfs
  Use inBound() to test if in the bound
  图的遍历(由点及面)
  小技巧：坐标变换数组:
  int[] deltaX = {1,0,0,-1}; int[] deltaY = {0,1,-1,0};
  并查集 Union Find在强化班
• Lintcode Knight Shortest Path
  http://www.lintcode.com/problem/knight-shortest-path/ http://www.jiuzhang.com/solutions/knight-shortest-path/
  简单图最短路径, follow up: speed up
• Related questions
  • Lintcode Zombie in Matrix
    http://www.lintcode.com/problem/zombie-in-matrix/
    https://www.jiuzhang.com/solutions/zombie-in-matrix/
    Coordinates and array
    {1,0,0,-1}{0,1,-1,0}
    Mark people as zombie for not accessible again
  • Lintcode 573.Build Post Office II
    http://www.lintcode.com/problem/build-post-office-ii/
    https://www.jiuzhang.com/solutions/?search=build%20post%20office

4 Topological sorting

四种问法：
求任意1个拓扑排序（Topological Order）
问是否存在拓扑排序（是否可以被拓扑排序）
求所有的拓扑排序（DFS）
求是否存在且仅存在一个拓扑排序 （Queue中最多同时只有1个节点）

• Lintcode 127.Topological Sorting
  http://www.lintcode.com/problem/topological-sorting/
  https://www.jiuzhang.com/solutions/topological-sorting/
  入度（In-degree）： 有向图（Directed Graph）中指向当前节点的点的个数（或指向当前节点的边的条数）
  算法描述：

  1. 统计每个点的入度
  2. 将每个入度为 0 的点放入队列（Queue）中作为起始节点
  3. 不断从队列中拿出一个点，去掉这个点的所有连边（指向其他点的边），其他点的相应的入度 - 1
  4. 一旦发现新的入度为 0 的点，丢回队列中
     拓扑排序并不是传统的排序算法 一个图可能存在多个拓扑序（Topological Order），也可能不存在任何拓扑序

• Leetcode 207/210.Course Schedule I && II
  https://leetcode.com/problemset/all/?search=couse%20schedule
  https://www.jiuzhang.com/solutions/?search=Course%20Schedule
  Course schedule I:
  Initial:
  Int[][] matrix = neighbors[pre][ready]; int[] indegree; List<> queue
  Course schedule II:
  Initial:
  Same as 1,int[] result, List<> queue ( return this list in int[] form)
  第二问需要判断是否没有拓扑序

• Leetcode 269.Alien Dictionary
  https://leetcode.com/problemset/all/?search=Alien%20Dictionary
  http://www.lintcode.com/problem/alien-dictionary/ http://www.jiuzhang.com/solution/alien-dictionary/
  考点：如何构建图，如何存储图，如何拓扑排序

• Leetcode 444.Sequence Reconstruction
  https://leetcode.com/problemset/all/?search=sequence%20reconstruction
  http://www.lintcode.com/problem/sequence-reconstruction/
  https://www.jiuzhang.com/solutions/?search=Sequence%20Reconstruction

5 Experience

• 能用 BFS 的一定不要用 DFS（除非面试官特别要求）
• BFS 的两个使用条件
  • 图的遍历（由点及面，层级遍历）
  • 简单图最短路径
• 是否需要层级遍历
  • size = queue.size()
• 拓扑排序必须掌握！
• 坐标变换数组
  • deltaX, deltaY
  • inBound

6 Template总结

1 Level order traversal

While(?queue.empty)
{Size = queue.size
For(i 0-size){}
} queue use queue and resultlist use poll and offer

2 Just BFS

For(i 0-size) queue use list get and add method

3 Use while

While(?queue.isEmpty()) { queue.poll(); loop(queue.offer());
}
Conclusion: 1 cost more time 2 cost more space, use 3 best(不使用index)
简单来说就是队列结构，但是可以有2个队列（层次遍历），或者1个队列，用for或者while来遍历