improved doc; improved code of union-find

dashidhy · dashidhy · commit 379f3c4e7e59 · 2020-08-03T10:03:02.000-07:00
diff --git a/README.md b/README.md
@@ -1,7 +1,5 @@
 # 算法模板
 
-![来刷题了](https://img.fuiboom.com/img/title.png)
-
 算法模板，最科学的刷题方式，最快速的刷题路径，一个月从入门到 offer，你值得拥有 🐶~
 
 算法模板顾名思义就是刷题的套路模板，掌握了刷题模板之后，刷题也变得好玩起来了~
diff --git a/basic_algorithm/graph/README.md b/basic_algorithm/graph/README.md
@@ -1,14 +1,12 @@
 # 图相关算法
 
-Ongoing...
+### [深度优先搜索和广度优先搜索](./bfs_dfs.md)
 
-[深度优先搜索和广度优先搜索](./bfs_dfs.md)
+### [拓扑排序](./topological_sorting.md)
 
-[拓扑排序](./topological_sorting.md)
+### [最小生成树](./mst.md)
 
-[最小生成树](./mst.md)
+### [最短路径](./shortest_path.md)
 
-[最短路径](./shortest_path.md)
-
-[图的表示](./graph_representation.md)
+### [图的表示](./graph_representation.md)
 
diff --git a/basic_algorithm/graph/bfs_dfs.md b/basic_algorithm/graph/bfs_dfs.md
@@ -180,7 +180,7 @@ class Solution:
                 for dr, dc in neighors:
                     nr, nc = r + dr, c + dc
                     if 0<= nr < M and 0 <= nc < N:
-                        if A[nr][nc] == 0: # meet and edge
+                        if A[nr][nc] == 0:
                             A[nr][nc] = -2
                             bfs.append((nr, nc))
                         elif A[nr][nc] == 1:
diff --git a/basic_algorithm/graph/mst.md b/basic_algorithm/graph/mst.md
@@ -4,7 +4,9 @@
 
 > 地图上有 m 条无向边，每条边 (x, y, w) 表示位置 m 到位置 y 的权值为 w。从位置 0 到 位置 n 可能有多条路径。我们定义一条路径的危险值为这条路径中所有的边的最大权值。请问从位置 0 到 位置 n 所有路径中最小的危险值为多少？
 
-最小危险值为最小生成树中 0 到 n 路径上的最大边权。
+最小危险值为最小生成树中 0 到 n 路径上的最大边权。以此题为例给出最小生成树的两种经典算法。
+
+- 算法 1: [Kruskal's algorithm]([https://en.wikipedia.org/wiki/Kruskal%27s_algorithm](https://en.wikipedia.org/wiki/Kruskal's_algorithm))，使用[并查集](../../data_structure/union_find.md)实现。
 
 ```Python
 # Kruskal's algorithm
@@ -13,6 +15,7 @@ class Solution:
         
         # Kruskal's algorithm with union-find
         parent = list(range(N + 1))
+        rank = [1] * (N + 1)
         
         def find(x):
             if parent[parent[x]] != parent[x]:
@@ -21,11 +24,18 @@ class Solution:
         
         def union(x, y):
             px, py = find(x), find(y)
-            if px != py:
+            if px == py:
+                return False
+            
+            if rank[px] > rank[py]:
+                parent[py] = px
+            elif rank[px] < rank[py]:
                 parent[px] = py
-                return True
             else:
-                return False
+                parent[px] = py
+                rank[py] += 1
+            
+            return True
         
         edges = sorted(zip(W, X, Y))
         
@@ -34,6 +44,8 @@ class Solution:
                 return w
 ```
 
+- 算法 2: [Prim's algorithm]([https://en.wikipedia.org/wiki/Prim%27s_algorithm](https://en.wikipedia.org/wiki/Prim's_algorithm))，使用[优先级队列 (堆)](../../data_structure/heap.md)实现
+
 ```Python
 # Prim's algorithm
 class Solution:
diff --git a/basic_algorithm/graph/shortest_path.md b/basic_algorithm/graph/shortest_path.md
@@ -105,14 +105,84 @@ class Solution:
                 for dr, dc in neighors:
                     nr, nc = r + dr, c + dc
                     if 0<= nr < M and 0 <= nc < N:
-                        if A[nr][nc] == 0: # meet and edge
+                        if A[nr][nc] == 0:
                             A[nr][nc] = -2
                             bfs.append((nr, nc))
                         elif A[nr][nc] == 1:
                             return flip
             flip += 1
 ```
 
+## Dijkstra's Algorithm
+
+用于求解单源最短路径问题。思想是 greedy 构造 shortest path tree (SPT)，每次将当前距离源点最短的不在 SPT 中的结点加入SPT，与构造最小生成树 (MST) 的 Prim's algorithm 非常相似。可以用 priority queue (heap) 实现。
+
+### [network-delay-time](https://leetcode-cn.com/problems/network-delay-time/)
+
+标准的单源最短路径问题，使用朴素的的 Dijikstra 算法即可，可以当成模板使用。
+
+```Python
+class Solution:
+    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
+        
+        # construct graph
+        graph_neighbor = collections.defaultdict(list)
+        for s, e, t in times:
+            graph_neighbor[s].append((e, t))
+        
+        # Dijkstra
+        SPT = {}
+        min_heap = [(0, K)]
+        
+        while min_heap:
+            delay, node = heapq.heappop(min_heap)
+            if node not in SPT:
+                SPT[node] = delay
+                for n, d in graph_neighbor[node]:
+                    if n not in SPT:
+                        heapq.heappush(min_heap, (d + delay, n))
+        
+        return max(SPT.values()) if len(SPT) == N else -1
+```
+
+### [cheapest-flights-within-k-stops](https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/)
+
+在标准的单源最短路径问题上限制了路径的边数，因此需要同时维护当前 SPT 内每个结点最短路径的边数，当遇到边数更小的路径 (边权和可以更大) 时结点需要重新入堆，以更新后继在边数上限内没达到的结点。
+
+```Python
+class Solution:
+    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
+        
+        # construct graph
+        graph_neighbor = collections.defaultdict(list)
+        for s, e, p in flights:
+            graph_neighbor[s].append((e, p))
+        
+        # modified Dijkstra
+        prices, steps = {}, {}
+        min_heap = [(0, 0, src)]
+        
+        while len(min_heap) > 0:
+            price, step, node = heapq.heappop(min_heap)
+            
+            if node == dst: # early return
+                return price
+
+            if node not in prices:
+                prices[node] = price
+            
+            steps[node] = step
+            if step <= K:
+                step += 1
+                for n, p in graph_neighbor[node]:
+                    if n not in prices or step < steps[n]:
+                        heapq.heappush(min_heap, (p + price, step, n))
+        
+        return -1
+```
+
+## 补充
+
 ## Bidrectional BFS
 
 当求点对点的最短路径时，BFS遍历结点数目随路径长度呈指数增长，为缩小遍历结点数目可以考虑从起点 BFS 的同时从终点也做 BFS，当路径相遇时得到最短路径。
@@ -182,81 +252,13 @@ class Solution:
         return 0
 ```
 
-## Dijkstra's Algorithm
-
-用于求解单源最短路径问题。思想是 greedy 构造 shortest path tree (SPT)，每次将当前距离源点最短的不在 SPT 中的结点加入SPT，与构造最小生成树 (MST) 的 Prim's algorithm 非常相似。可以用 priority queue (heap) 实现。
-
-### [network-delay-time](https://leetcode-cn.com/problems/network-delay-time/)
-
-标准的单源最短路径问题，使用朴素的的 Dijikstra 算法即可，可以当成模板使用。
-
-```Python
-class Solution:
-    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
-        
-        # construct graph
-        graph_neighbor = collections.defaultdict(list)
-        for s, e, t in times:
-            graph_neighbor[s].append((e, t))
-        
-        # Dijkstra
-        SPT = {}
-        min_heap = [(0, K)]
-        
-        while min_heap:
-            delay, node = heapq.heappop(min_heap)
-            if node not in SPT:
-                SPT[node] = delay
-                for n, d in graph_neighbor[node]:
-                    if n not in SPT:
-                        heapq.heappush(min_heap, (d + delay, n))
-        
-        return max(SPT.values()) if len(SPT) == N else -1
-```
-
-### [cheapest-flights-within-k-stops](https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/)
-
-在标准的单源最短路径问题上限制了路径的边数，因此需要同时维护当前 SPT 内每个结点最短路径的边数，当遇到边数更小的路径 (边权和可以更大) 时结点需要重新入堆，以更新后继在边数上限内没达到的结点。
-
-```Python
-class Solution:
-    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
-        
-        # construct graph
-        graph_neighbor = collections.defaultdict(list)
-        for s, e, p in flights:
-            graph_neighbor[s].append((e, p))
-        
-        # modified Dijkstra
-        prices, steps = {}, {}
-        min_heap = [(0, 0, src)]
-        
-        while len(min_heap) > 0:
-            price, step, node = heapq.heappop(min_heap)
-            
-            if node == dst: # early return
-                return price
-
-            if node not in prices:
-                prices[node] = price
-            
-            steps[node] = step
-            if step <= K:
-                step += 1
-                for n, p in graph_neighbor[node]:
-                    if n not in prices or step < steps[n]:
-                        heapq.heappush(min_heap, (p + price, step, n))
-        
-        return -1
-```
-
-## 补充：A* Algorithm
+## A* Algorithm
 
 当需要求解有目标的最短路径问题时，BFS 或 Dijkstra's algorithm 可能会搜索过多冗余的其他目标从而降低搜索效率，此时可以考虑使用 A* algorithm。原理不展开，有兴趣可以自行搜索。实现上和 Dijkstra’s algorithm 非常相似，只是优先级需要加上一个到目标点距离的估值，这个估值严格小于等于真正的最短距离时保证得到最优解。当 A* algorithm 中的距离估值为 0 时 退化为 BFS 或 Dijkstra’s algorithm。
 
 ### [sliding-puzzle](https://leetcode-cn.com/problems/sliding-puzzle)
 
-思路 1：BFS。为了方便对比 A* 算法写成了与其相似的形式。
+- 方法 1：BFS。为了方便对比 A* 算法写成了与其相似的形式。
 
 ```Python
 class Solution:
@@ -300,7 +302,7 @@ class Solution:
         return -1
 ```
 
-思路 2：A* algorithm
+- 方法 2：A* algorithm
 
 ```Python
 class Solution:
diff --git a/basic_algorithm/graph/topological_sorting.md b/basic_algorithm/graph/topological_sorting.md
@@ -6,10 +6,11 @@
 
 > 给定课程的先修关系，求一个可行的修课顺序
 
-非常经典的拓扑排序应用题目。下面给出 3 种实现方法，可以当做模板使用。
+非常经典的拓扑排序应用。下面给出 3 种实现方法，可以当做模板使用。
+
+- 方法 1：DFS 的递归实现
 
 ```Python
-# 方法 1：DFS 的递归实现
 NOT_VISITED = 0
 DISCOVERING = 1
 VISITED = 2
@@ -42,8 +43,9 @@ class Solution:
         return tsort_rev[::-1]
 ```
 
+- 方法 2：DFS 的迭代实现
+
 ```Python
-# 方法 2：DFS 的迭代实现
 NOT_VISITED = 0
 DISCOVERING = 1
 VISITED = 2
@@ -81,8 +83,9 @@ class Solution:
         return tsort_rev[::-1]
 ```
 
+- 方法 3：[Kahn's algorithm](https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm)
+
 ```Python
-# 方法 3：Kahn's algorithm: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
 class Solution:
     def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
         
diff --git a/data_structure/union_find.md b/data_structure/union_find.md
