Prim's Algorithm
Prim's Algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) for a weighted, connected, and undirected graph. The algorithm builds the MST by starting from an arbitrary vertex and iteratively adding the smallest edge that connects a vertex in the tree to a vertex outside the tree.
1 Definition[편집 | 원본 편집]
Given a weighted, connected, undirected graph G = (V, E), Prim's Algorithm constructs a spanning tree T such that the total weight of the edges in T is minimized. At each step, the algorithm selects the edge with the lowest weight that connects a vertex in T to a vertex not yet in T.
2 Concept[편집 | 원본 편집]
Prim's Algorithm works on the following principles:
- Initialization: Start with an arbitrary vertex; mark it as part of the MST.
- Edge Selection: Among all edges that connect vertices in the MST to those not in the MST, select the edge with the smallest weight.
- Expansion: Add the selected edge and the new vertex to the MST.
- Repeat: Continue the process until all vertices are included in the MST.
3 Algorithm Steps[편집 | 원본 편집]
- Initialize the MST with a starting vertex.
- While the MST does not contain all vertices:
- Find the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST.
- Add the selected edge and the corresponding vertex to the MST.
- End While
Example[편집 | 원본 편집]
Consider the following weighted graph:
Vertex Pair | Edge Weight |
---|---|
A - B | 4 |
A - C | 3 |
B - C | 1 |
B - D | 2 |
C - D | 5 |
One possible execution of Prim's Algorithm starting at vertex A:
- Start with vertex A.
- The available edges are A - B (4) and A - C (3). Choose A - C (3) because 3 is the smallest.
- Now the MST contains A and C. The available edges are A - B (4), C - B (1), and C - D (5). Choose C - B (1).
- MST now contains A, C, and B. The remaining available edge is B - D (2) and C - D (5). Choose B - D (2).
- The MST now includes all vertices with the edges A - C (3), C - B (1), and B - D (2). The total weight is 3 + 1 + 2 = 6.
Implementation[편집 | 원본 편집]
A simple implementation of Prim's Algorithm in Python:
import heapq
def prim_mst(graph, start):
mst = []
visited = set([start])
# Priority queue: (edge_weight, from_vertex, to_vertex)
edges = [(weight, start, to) for to, weight in graph[start].items()]
heapq.heapify(edges)
while edges:
weight, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to, weight))
for next_to, next_weight in graph[to].items():
if next_to not in visited:
heapq.heappush(edges, (next_weight, to, next_to))
return mst
# Example graph represented as an adjacency dictionary
graph = {
'A': {'B': 4, 'C': 3},
'B': {'A': 4, 'C': 1, 'D': 2},
'C': {'A': 3, 'B': 1, 'D': 5},
'D': {'B': 2, 'C': 5}
}
mst = prim_mst(graph, 'A')
print("Minimum Spanning Tree:", mst)
Advantages[편집 | 원본 편집]
- Greedy Approach – Always selects the smallest available edge.
- Efficient for Dense Graphs – Performs well when there are many edges.
- Simple Implementation – Easy to understand and implement.
Limitations[편집 | 원본 편집]
- Requires a Connected Graph – Prim's Algorithm works only on connected graphs.
- Potential for High Memory Usage – Maintaining a priority queue can require extra memory in very large graphs.
Applications[편집 | 원본 편집]
- Network Design – Used in designing efficient communication, transportation, or power networks.
- Cluster Analysis – Forms the basis for some hierarchical clustering techniques.
- Approximation Algorithms – Serves as a component in algorithms for solving NP-hard problems like the Traveling Salesman Problem.