Algorithm Design Questions
Prim's algorithm is a greedy algorithm used to find a minimum spanning tree in a weighted undirected graph. It starts with an arbitrary vertex and repeatedly adds the edge with the minimum weight that connects a vertex in the current tree to a vertex outside the tree.
The algorithm works as follows:
1. Initialize an empty tree and a set of visited vertices.
2. Choose an arbitrary vertex as the starting point and add it to the tree.
3. While there are still unvisited vertices:
a. Find the minimum weight edge that connects a vertex in the tree to a vertex outside the tree.
b. Add the selected edge and the corresponding vertex to the tree.
c. Mark the newly added vertex as visited.
4. Repeat step 3 until all vertices are visited.
The algorithm terminates when all vertices are visited, resulting in a minimum spanning tree that connects all vertices with the minimum total weight.