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
2. add an edge has following properties:

• doesn’t form a cycle if it’s added to the tree
• incident to one of vertices in the tree
• has the smallest weight.

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.
2. w(e1) = w(e2): (T-{e1})⋃{e2} =T’. So T is also one of the solutions.
3. w(e1) < w(e2): It’s impossible because the algorithm always finds the edge with the smallest weight.

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