Minimum Spanning Tree

prims.py

from fibHeap import FibonacciHeap #https://github.com/Agnishom/fibonacci-heap-python/

def prims(adjList, source = 1):
    n = len(adjList)    #intentionally 1 more than the number of vertices, keep the 0th entry free for convenience
    visited = [False]*n
    parent = [None]*n
    cost = [float('inf')]*n

    heapNodes = [None]*n
    heap = FibonacciHeap()
    for i in range(1, n):
        heapNodes[i] = heap.insert(float('inf'), i)     # cost, label

    cost[source] = 0
    heap.decrease_key(heapNodes[source], 0)

    while heap.total_nodes:
        current = heap.extract_min().value
        visited[current] = True

        for (neighbor, edgeCost) in adjList[current]:
            if not visited[neighbor]:
                if edgeCost < cost[neighbor]:
                    cost[neighbor] = edgeCost
                    parent[neighbor] = (current, edgeCost) #parent, cost
                    heap.decrease_key(heapNodes[neighbor], edgeCost)

    return parent

# Graph here
# https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif

# Convention: Avoid 0-indexing. Keep 0th entry unused if necessary
# Convention: adjList[i] = [(neighbor, weight) for all neighbors]

'''
adjList = [
[],
[(2, 7), (3, 9), (6, 14)],
[(1, 7), (4, 15), (3, 10)],
[(1, 9), (2, 10), (4, 11), (6, 2)],
[(2, 15), (3, 11), (5, 6)],
[(4, 6), (6, 9)],
[(5, 9), (1, 14)]
]
'''