743-network-delay-time.md Added DFS, BFS, UnionFind into comparison table.

gazeldx · gazeldx · commit 86aead2e44a3 · 2025-02-18T15:10:55.000+08:00
diff --git a/en/1-1000/743-network-delay-time.md b/en/1-1000/743-network-delay-time.md
@@ -56,12 +56,15 @@ For a detailed description of **Dijkstra's algorithm**, please refer to [1514. P
 ### Common graph theory algorithm comparison table
 |Algorithm name|Main application scenarios|Optimization methods|Importance|Difficulty|min_<br>distances|Negative weights|Additional application scenarios|
 |--------------|--------------------------|--------------------|----------|----------|-------------|----------------|--------------------------------|
-|[Prim's algorithm](../1001-2000/1584-min-cost-to-connect-all-points.md)                                           |Minimum Spanning Tree      |Heap Sort Simplify|Important     |Medium         |Used    |Can handle||
-|[Kruskal's algorithm](../1001-2000/1584-min-cost-to-connect-all-points-2.md)                                      |Minimum Spanning Tree      |No need           |important     |Relatively hard|Not used|Can handle|Relative: [Undirected Graph Cycle Detection](./684-redundant-connection.md), [Directed Graph Cycle Detection](./685-redundant-connection-ii.md)|
-|[Dijkstra's algorithm](../1001-2000/1514-path-with-maximum-probability.md)                                        |Single-Source Shortest Path|Heap Sort         |Very important|Relatively hard|Used    |Cannot handle||
-|[A* search algorithm](./752-open-the-lock.md)                                                                     |Single-Source Shortest Path|Built-in Heap Sort|Very important|Medium         |Not used|It depends||
-|[Bellman-Ford algorithm](./743-network-delay-time.md)                                                             |Single-Source Shortest Path|Queue-Improved    |Very Important|Easy           |Used    |Can handle|[Detect Negative Cycles](https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/), <br>[Shortest Hop-Bounded Paths](./787-cheapest-flights-within-k-stops.md)|
-|[Floyd–Warshall](../1001-2000/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md)|Multi-Source Shortest Path |No need           |Less important|Relatively hard|Used    |Can handle||
+|[Depth-first search](./797-all-paths-from-source-to-target.md)                                                    |Traverse a graph           |No need              |Very important|Easy          |No need |Can handle||
+|[Breath-first search](../1001-2000/1971-find-if-path-exists-in-graph.md)                                          |Traverse a graph           |No need              |Very important|Easy          |No need |Can handle|Single-Source Shortest Path if No Weight|
+|[UnionFind, aka disjoint-set](./684-redundant-connection.md)                                                      |Graph Connectivity         |Path Compression     |Very important|Medium        |No need |Can handle|[Directed Graph Cycle Detection](./685-redundant-connection-ii.md)|
+|[Prim's algorithm](../1001-2000/1584-min-cost-to-connect-all-points.md)                                           |Minimum Spanning Tree      |Heap Sort to Simplify|Important     |Medium         |Used   |Can handle||
+|[Kruskal's algorithm](../1001-2000/1584-min-cost-to-connect-all-points-2.md)                                      |Minimum Spanning Tree      |No need              |Important     |Relatively hard|No need|Can handle||
+|[Dijkstra's algorithm](../1001-2000/1514-path-with-maximum-probability.md)                                        |Single-Source Shortest Path|Heap Sort            |Very important|Relatively hard|Used   |Cannot handle||
+|[A* search algorithm](./752-open-the-lock.md)                                                                     |Single-Source Shortest Path|Built-in Heap Sort   |Very important|Medium         |No need|It depends||
+|[Bellman-Ford algorithm](./743-network-delay-time.md)                                                             |Single-Source Shortest Path|Queue-Improved       |Very Important|Easy           |Used   |Can handle|[Detect Negative Cycles](https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/), <br>[Shortest Hop-Bounded Paths](./787-cheapest-flights-within-k-stops.md)|
+|[Floyd–Warshall](../1001-2000/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md)|Multi-Source Shortest Path |No need              |Less important|Relatively hard|Used   |Can handle||
 
 ## Complexity
 **V**: vertex count, **E**: Edge count.
diff --git a/en/1001-2000/1971-find-if-path-exists-in-graph.md b/en/1001-2000/1971-find-if-path-exists-in-graph.md
@@ -94,7 +94,7 @@ class Solution:
         return False
 ```
 
-### Depth-first search
+### Depth-first search (more complex)
 ```python
 class Solution:
     def __init__(self):
diff --git a/en/3001-4000/unorganized.md b/en/3001-4000/unorganized.md
@@ -59,11 +59,14 @@ The improved way with a queue is commonly more efficient. Relaxing **All Edges**
 * The time complexity of `Floyd–Warshall algorithm` is `V * V * V`. For a dense graph, `Floyd–Warshall algorithm` is still faster.
 * `A* algorithm` use a `priority queue`, `pop()` to get the vertex closest to the destination vertex. We need to choose **proper math formula** to determine which one is the closest. We to the very near place of destination vertex, we can use some special method to make it can handle the last part.  
 
-|Algorithm name|Focus|Key implementation methods|
+|Algorithm name|Focus|Key implementation methods|mark visited|
 |Prim's algorithm|Vertices||
 |Kruskal's algorithm|Edges|Union-Find|
 |Dijkstra's algorithm|Vertices||
 |Bellman-Ford algorithm|Edges(Vertices+Edges for SPFA)||
+|Dijkstra's by heap sort - min_distance = A*|
+UnionFind + Heap sort = Kruskal
+BFS + heap sort = A*
 
 Add a table to show the differences between A-Start and breadth-first search
 
diff --git a/zh/1-1000/743-network-delay-time.md b/zh/1-1000/743-network-delay-time.md
@@ -58,9 +58,12 @@
 
 |算法名称|主要的适用场景|优化方式|重要度|难度|min_<br>distances|负边权值|额外的适用场景|
 |-------|-----------|-------|-------|---|-------------|--------|------------|
-|[Prim算法](../1001-2000/1584-min-cost-to-connect-all-points.md)                                                    |最小生成树 |堆排序简化|重要   |中等|用到|能处理||
-|[Kruskal算法](../1001-2000/1584-min-cost-to-connect-all-points-2.md)                                               |最小生成树 |无需优化  |重要   |较难|不用|能处理|相关：[无向图环检测](./684-redundant-connection.md), [有向图环检测](./685-redundant-connection-ii.md)|
-|[Dijkstra算法](../1001-2000/1514-path-with-maximum-probability.md)                                                 |单源最短路径|堆排序优化|很重要 |较难|用到|无能力||
+|[深度优先搜索](./797-all-paths-from-source-to-target.md)                                                            |遍历图     |无需优化  |很重要 |简单|不用|能处理||
+|[广度优先搜索](../1001-2000/1971-find-if-path-exists-in-graph.md)                                                   |遍历图     |无需优化  |很重要 |简单|不用|能处理|不考虑权时，可用于求单源最短路径|
+|[并查集](./684-redundant-connection.md)                                                                            |检测图的连通性|路径压缩|很重要 |中等|不用|能处理|[有向图环检测](./685-redundant-connection-ii.md)|
+|[Prim 算法](../1001-2000/1584-min-cost-to-connect-all-points.md)                                                   |最小生成树 |堆排序简化|重要   |中等|用到|能处理||
+|[Kruskal 算法](../1001-2000/1584-min-cost-to-connect-all-points-2.md)                                              |最小生成树 |无需优化  |重要   |较难|不用|能处理||
+|[Dijkstra 算法](../1001-2000/1514-path-with-maximum-probability.md)                                                |单源最短路径|堆排序优化|很重要 |较难|用到|无能力||
 |[A* 算法](./752-open-the-lock.md)                                                                                  |单源最短路径|固有堆排序|很重要 |中等|不用|看情况||
 |[Bellman-Ford](./743-network-delay-time.md)                                                                       |单源最短路径|集合优化  |很重要 |简单|用到|能处理|[负环检测](https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/), [限定步数最短路径](./787-cheapest-flights-within-k-stops.md)|
 |[Floyd–Warshall](../1001-2000/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md)|多源最短路径|无需优化  |较不重要|较难|用到|能处理||
