Prim's algorithm starts with an arbitrary node and greedily grows the minimum spanning tree by adding the edge with the smallest weight.
import heapq
def prim(graph):
start_vertex = list(graph.keys())[0]
visited = set([start_vertex])
edges = [
(cost, start_vertex, to)
for to, cost in graph[start_vertex].items()
]
heapq.heapify(edges)
minimum_spanning_tree = []
while edges:
cost, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
minimum_spanning_tree.append((frm, to, cost))
for to_next, cost in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (cost, to, to_next))
return minimum_spanning_tree
# Example Usage:
graph = {0: {1: 4, 2: 2}, 1: {0: 4, 3: 5}, 2: {0: 2, 3: 8}, 3: {1: 5, 2: 8}}
minimum_spanning_tree = prim(graph)
print(minimum_spanning_tree)
