Skip to content

12.Greedy.md

Latest commit

 

History

History
43 lines (29 loc) · 1.67 KB

12.Greedy.md

File metadata and controls

43 lines (29 loc) · 1.67 KB

Greedy

  1. Jump Game II
  2. Video Stitching
  3. Minimum Number of Taps to Open to Water a Garden
  4. Partition Labels

生成树(Spanning Tree), prim求最小生成树

Prim’s Minimum Spanning Tree (MST) Kruskal’s Minimum Spanning Tree Algorithm

Prim算法原理： 1）以某一个点开始，寻找当前该点可以访问的所有的边； 2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边； 3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入； 4）此时由所有边构成的树即为最小生成树。

Kruskal

思想： 给所有权重排序，每次选择权重最小的边，将node连接起来. 如果连接后会产生cycle，就不连接那一条边. 直到所有的点都连接起来了.

  1. Sort all the edges in non-decreasing order of their weight.
  2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
  3. Repeat step#2 until there are (V-1) edges in the spanning tree.

有向图的最短路径

Dijkstra’s Algorithm 注意:Dijkstra算法只能做路径为positive的情况. Dijkstra’s algorithm solves the single-source shortest-paths problem on a directed weighted graph G = (V, E), where all the edges are non-negative (i.e., w(u, v) ≥ 0 for each edge (u, v) Є E).

思想： 从加入起始点开始visited=[]，更新能到达的结点，选取最小的节点，继续更新能够到达的节点，直到加入所有结点到visited。

Bellman Ford Algorithm