Prim's Algorithm

• Greedy algo
• used to get Minimum Spanning Tree
• Weighted connected graph
• Minimum path length (wire length if nodes are devices) to make sure all nodes are connected to each other maybe through intermediate nodes
• Time $O(V^2)$, Space: $O(V)$

Pseudo Code:

- maintain a set of MST
- add new vertex by adding the one with min weight (greedy)

Python

def primMST(graph):
    V = len(graph)
    key = [float('inf')] * V
    key[0] = 0
    res = 0
    mSet = [False] * V
    for _ in range(V):
        u = -1
        for v in range(V):
            if not mSet[v] and (u == -1 or key[v] < key[u]):
                u = i
        mSet[u] = True
        res += key[u]
        for v in range(V):
            if not mSet[v] and graph[u][v] != 0 and graph[u][v] < key[v]:
                key[v] = graph[u][v]
    return res

info

• The above is not the best most efficient implementation.
• We use adj list (don't have to travel the whole row)
• min heap (find min weight edge in log V)
• Time - $O(E log V)$