How to find MST and show if the given algorithms are correct? Here’s the answer:

When given a graph, MST(Minimum Spanning Tree) refers to a subset of edges with a minimum sum of edge costs. There’re several ways to find MST such as Prim’s algorithm, Kruskal’s algorithm, and Dijkstra’s algorithm.

Prim’s algorithm

Prim’s algorithm runs in the following way:

  1. starts from any vertex in the tree
  • doesn’t form a cycle if it’s added to the tree

3. If the tree became a spanning tree, then exit. Otherwise, go to (1) and repeat.

Proof of Prim’s algorithm

The tree found by the algorithm: T, one of the possible solution trees: T’. if T = T’, the algorithm finds the solution. Otherwise, let’s call an edge e_1 that T’ doesn’t have and is found first while executing the algorithm. When e_1 is represented as (u,v), suppose e_2 is an edge that belongs to T’ and incident to either u or v. depending on the value of e1 and e2, one of these cases occurs.

  1. w(e1) > w(e2): (T’-{e1})⋃{e2} can result in smaller sum of edge weights. contradictory to the condition that T’ is the solution.

Therefore, Prim’s algorithm finds MST(Minimal Spanning Tree).