Prim’s algorithm for finding MST

Prim’s algorithm for finding MST (Minimum Spanning Tree)

Prim's algorithm to find minimum cost spanning tree uses the greedy approach. Prim's algorithm, in contrast with Kruskal's algorithm, treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph.

Example:

Step 1 - Remove all loops and parallel edges. 

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Choose any arbitrary node as root node

In this case, we choose S node as the root node of Prim's spanning tree. This node is arbitrarily chosen, so any node can be the root node. 

Step 3 - Check outgoing edges and select the one with less cost

After choosing the root node S, we see that S,A and S,C are two edges with weight 7 and 8, respectively. We choose the edge S,A as it is lesser than the other.

We check for all edges going out from (S,A). We select the one which has the lowest cost and include it in the tree.

This process is repeated until all the nodes in the graph are covered.

Example 2:

Kruskal’s algorithm for finding MST

Kruskal’s algorithm for finding MST(Minimum Spanning Tree)

Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach.

To understand Kruskal's algorithm let us consider the following example –

Step 1 - Remove all loops and Parallel Edges

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Arrange all edges in their increasing order of weight

Step 3 - Add the edge which has the least weightage

Now we start adding edges to the graph beginning from the one which has the least weight. Throughout, we shall keep checking that the spanning properties remain intact. In case, by adding one edge, the spanning tree property does not hold (forms a cycle) then we shall not include the edge in the graph.

The least cost is 2 and edges involved are B,D and D,T. We add them.

Next cost is 3, and associated edges are A,C and C,D. We add them again –

Next cost in the table is 4, and we observe that adding it will create a circuit in the graph. We ignore it.

We observe that edges with cost 5 and 6 also create circuits. We ignore them and move on.

Now we are left with only one node to be added. Between the two least cost edges available 7 and 8, we shall add the edge with cost 7.

By adding edge S,A we have included all the nodes of the graph and we now have minimum cost spanning tree.

Example 2:

Minimum Spanning Tree (MST)

Minimum Spanning Tree (MST)

Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees.

A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

Following are a few properties of the spanning tree connected to graph G −

• A connected graph G can have more than one spanning tree.
• All possible spanning trees of graph G, have the same number of edges and vertices.
• The spanning tree does not have any cycle (loops).
• Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning tree is minimally connected.
• Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is maximally acyclic.

Mathematical Properties of Spanning Tree

• Spanning tree has n-1 edges, where n is the number of nodes (vertices).
• From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.
• A complete graph can have maximum n^n-2 number of spanning trees.

A complete undirected graph can have maximum n^n-2 number of spanning trees, where n is the number of nodes. In the below given example, n is 3, hence 3³⁻² = 3spanning trees are possible.

A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.

Two most important spanning tree algorithms here −

• Kruskal's Algorithm
• Prim's Algorithm