Prim's Algorithm: Understanding and Applying MST Algorithms

This assignment explores Prim's Algorithm, a method used to find the Minimum Spanning Tree (MST) in a graph. The solution details the steps involved, including removing self-loops and parallel edges, selecting a root node, and iteratively choosing edges with the least weight. The assignment also contrasts Prim's Algorithm with the Brute Force approach, highlighting their respective pros and cons. Prim's Algorithm is faster, while Brute Force provides optimal solutions but is inefficient for larger graphs. The solution provides a detailed explanation of both algorithms, their implementation, and their comparative analysis. It explains the algorithm's application and significance in data science and related fields.

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.