Prim's Algorithm

IT 위키

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:

  1. Initialization: Start with an arbitrary vertex; mark it as part of the MST.
  2. Edge Selection: Among all edges that connect vertices in the MST to those not in the MST, select the edge with the smallest weight.
  3. Expansion: Add the selected edge and the new vertex to the MST.
  4. Repeat: Continue the process until all vertices are included in the MST.

3 Algorithm Steps[편집 | 원본 편집]

  1. Initialize the MST with a starting vertex.
  2. 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.
  3. 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:

  1. Start with vertex A.
  2. The available edges are A - B (4) and A - C (3). Choose A - C (3) because 3 is the smallest.
  3. 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).
  4. MST now contains A, C, and B. The remaining available edge is B - D (2) and C - D (5). Choose B - D (2).
  5. 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.

See Also[편집 | 원본 편집]