Greedy Algorithms Questions
Prim's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected weighted graph. The algorithm starts with an arbitrary vertex and repeatedly adds the minimum weight edge that connects a vertex in the MST to a vertex outside the MST.
The steps of Prim's algorithm are as follows:
1. Initialize an empty MST and a set of visited vertices.
2. Choose an arbitrary vertex as the starting point and mark it as visited.
3. Repeat the following steps until all vertices are visited:
a. Find the minimum weight edge that connects a visited vertex to an unvisited vertex.
b. Add this edge to the MST and mark the unvisited vertex as visited.
4. Return the MST.
The algorithm continues until all vertices are visited, resulting in a tree that spans all the vertices with the minimum total weight.