Prim's Algorithm

  • Start from some arbitrary start node.

    • Repeatedly add shortest edge (mark black) that has one node inside the MST under construction.
    • Repeat until V-1 edges.

  • Demo: https://docs.google.com/presentation/d/1NFLbVeCuhhaZAM1z3s9zIYGGnhT4M4PWwAc-TLmCJjc/edit#slide=id.g9a60b2f52_0_0

    • Insert all vertices into fringe PQ, storing vertices in order of distance from source.
    • Repeat: Remove (closest) vertex v from PQ, and relax all edges pointing from v.
    • 将所有顶点插入流苏PQ，按照与源头的距离顺序存储顶点。
    • 重复：从PQ中移除（最近的）顶点v，并放松所有指向v的边。

  • It is important to note that MST is not unique.

  • Why does Prim’s work? Special case of generic algorithm.

    • Suppose we add edge e = v->w.
    • Side 1 of cut is all vertices connected to start, side 2 is all the others.
    • No crossing edge is black (all connected edges on side 1).
    • No crossing edge has lower weight (consider in increasing order).

  • This is one algorithm to find a MST from a Graph. It is as follows:

  1. Start from some arbitrary start node.
  2. Repeatedly add the shortest edge that has one node inside the MST under construction.
  3. Repeat until there are V-1 edges.

Essentially, this algorithm runs via the same mechanism as Dijkstra's algorithm, but while Dijkstra's considers candidate nodes by their distance from the source node, Prim's looks at each candidate node's distance from the MST under construction.

Thus, the runtime of Prim's if done using the same mechanism as Dijkstra's, would be the same as Dijkstra's, which is O((|V|+|E|) \log |V|)O((∣V∣+∣E∣)log∣V∣).
Remember, this is because we need to add to a Priority Queue fringe once for every edge we have, and we need to dequeue from it once for every vertex we have.