Minimum Cost Spanning Tree Algorithm

Prim's Algorithm and Brute Force Algorithm are two approaches to find the minimum cost spanning tree in a graph. Prim's Algorithm uses a greedy approach, starting with an arbitrary node, selecting the edge with the least weight until all nodes are included. It has the advantage of being faster than Brute Force but may not always provide the optimal solution. On the other hand, Brute Force Algorithm involves listing all possible Hamilton circuits, calculating their weights, and choosing the one with the smallest weight. While it can give an optimal solution, it is inefficient and only practical for small graphs.

Prim’s Algorithm:
This algorithm is used to find minimum cost spanning tree. This algorithm uses greedy approach.
Prim’s algorithm treats each node in the given graph as single tree and search for less weighted
edge. Here are some steps that are followed using this algorithm,
1. First all loops (self-loops) are removed and parallel edges.
2. Choose an arbitrary node as root node randomly.
3. Checking outgoing edges and select the one with less cost or less weight.
4. And the process in the point 3 will be continued until we reach at the end of the given
undirected graph. Through this method we will get a spanning tree with the shortest part.
Pros:
 This algorithm is faster than the Brute Force.
Cons:
 This algorithm may not give optimal solution in comparison of Brute Force Algorithm.
Brute Force Algorithm
Here are some steps,
1. According to this algorithm we first list all possible Hamilton circuits ( means learning
out the exact reversals, if you wish )
2. Then calculate weight of each circuits
3. Choose the one with the smallest weight.
Pros:
 This algorithms always work if there is enough time and care.
 Easy to understand and implement.
 It can give an optimal (best) solution.

Cons:
 This algorithm can only be applied for relatively small graphs.
 Not a practical algorithm in many cases.
 This is inefficient algorithm.