Finds the Minimum Spanning Tree (MST) of a graph.

• Initialize: Start with an arbitrary vertex as the initial MST.
• Grow MST: At each step, add the cheapest edge that connects a vertex in the MST to a vertex outside the MST.
• Repeat: Continue this process until all vertices are included in the MST.

It maintains a priority queue (min-heap) to efficiently select the next edge to add to the MST.

USE CASES

• Network Design: Designing communication networks, such as laying cables, to minimize the total cost while ensuring connectivity.
• Cluster Analysis: Data analysis to identify groups of similar data points.
• Approximate Solutions: Approximate solutions for optimization problems such as the Traveling Salesman Problem.
• Routing Protocols: Routing protocols for finding efficient paths in computer networks.
• Power Grid Design: Designing power distribution networks to minimize energy loss.

Python

def prim(graph):
    n = len(graph)
    visited = [False] * n
    min_heap = [(0, 0)]  # (weight, vertex)
    mst = []

    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True

        mst.append((u, weight))

        for v, w in graph[u].items():
            if not visited[v]:
                heapq.heappush(min_heap, (w, v))

    return mst