11. Minimum Spanning Tree using Prims Algorithm using Priority Queue

Prim's Algorithm - Minimum Spanning Tree using Priority Queue¶

• A slightly different version of Priority Queue

In [1]:

class MinHeapPriorityQueue:
    def __init__(self, arr=None):
        self.heap = []
        self.heap_size = 0
        self.pos = []
        if arr is not None:
            self.heap = arr
            self.heap_size = len(self.heap)
            self.pos = list(range(len(arr)))

    def min_heapify(self, parent):
        smallest = parent
        left_child = 2 * parent + 1
        right_child = 2 * parent + 2

        if (
            left_child < self.heap_size
            and self.heap[parent][1] > self.heap[left_child][1]
        ):
            smallest = left_child
        if (
            right_child < self.heap_size
            and self.heap[smallest][1] > self.heap[right_child][1]
        ):
            smallest = right_child

        if smallest != parent:
            self.pos[smallest], self.pos[parent] = self.pos[parent], self.pos[smallest]

            self.swap(smallest, parent)
            # heapify again the one which has been moved
            self.min_heapify(smallest)

    def insert_min_heap(self, key, weight):
        self.heap.append([key, weight])
        self.pos.append(self.heap_size)
        self.heap_size += 1

        n = (self.heap_size // 2) - 1
        for node in range(n, -1, -1):
            self.min_heapify(node)

    def swap(self, idx_a, idx_b):
        self.heap[idx_a], self.heap[idx_b] = (self.heap[idx_b], self.heap[idx_a])

    def build_min_heap(self):
        n = (self.heap_size // 2) - 1
        for node in range(n, -1, -1):
            self.min_heapify(node)

    def get_min_root(self):
        if self.heap_size > 0:

            element = self.heap.pop(0)
            idx = element[0]
            self.pos.remove(idx)
            self.heap_size -= 1
            self.min_heapify(0)
            return element
        else:
            print("Heap is empty")

    # # * In min heap pq, increase key means push down
    # # * push down means heapify
    # # * heapify means min_heapify
    # def increase_key(self, index, key):
    #     self.heap[index] = key
    #     self.min_heapify(index)

    # In min heap pq, decrease key means push up
    # push up means swap current node with parent
    # do ... until the node is greater than the parent
    # when we are pushing up, we will always move towards zero index
    # or root
    def decrease_key(self, index, key):
        # get position of index in pos array
        poi = self.pos.index(index)

        self.heap[poi][1] = key

        while (poi > 0) and self.heap[(poi - 1) // 2][1] > self.heap[poi][1]:
            self.pos[poi], self.pos[(poi - 1) // 2] = (
                self.pos[(poi - 1) // 2],
                self.pos[poi],
            )
            self.swap(poi, (poi - 1) // 2)
            poi = (poi - 1) // 2

    def is_empty(self):
        return True if self.heap_size == 0 else False

    def is_in_heap(self, v):
        if v in self.pos:
            if self.pos.index(v) < self.heap_size:
                return True
        return False

class MinHeapPriorityQueue: def __init__(self, arr=None): self.heap = [] self.heap_size = 0 self.pos = [] if arr is not None: self.heap = arr self.heap_size = len(self.heap) self.pos = list(range(len(arr))) def min_heapify(self, parent): smallest = parent left_child = 2 * parent + 1 right_child = 2 * parent + 2 if ( left_child < self.heap_size and self.heap[parent][1] > self.heap[left_child][1] ): smallest = left_child if ( right_child < self.heap_size and self.heap[smallest][1] > self.heap[right_child][1] ): smallest = right_child if smallest != parent: self.pos[smallest], self.pos[parent] = self.pos[parent], self.pos[smallest] self.swap(smallest, parent) # heapify again the one which has been moved self.min_heapify(smallest) def insert_min_heap(self, key, weight): self.heap.append([key, weight]) self.pos.append(self.heap_size) self.heap_size += 1 n = (self.heap_size // 2) - 1 for node in range(n, -1, -1): self.min_heapify(node) def swap(self, idx_a, idx_b): self.heap[idx_a], self.heap[idx_b] = (self.heap[idx_b], self.heap[idx_a]) def build_min_heap(self): n = (self.heap_size // 2) - 1 for node in range(n, -1, -1): self.min_heapify(node) def get_min_root(self): if self.heap_size > 0: element = self.heap.pop(0) idx = element[0] self.pos.remove(idx) self.heap_size -= 1 self.min_heapify(0) return element else: print("Heap is empty") # # * In min heap pq, increase key means push down # # * push down means heapify # # * heapify means min_heapify # def increase_key(self, index, key): # self.heap[index] = key # self.min_heapify(index) # In min heap pq, decrease key means push up # push up means swap current node with parent # do ... until the node is greater than the parent # when we are pushing up, we will always move towards zero index # or root def decrease_key(self, index, key): # get position of index in pos array poi = self.pos.index(index) self.heap[poi][1] = key while (poi > 0) and self.heap[(poi - 1) // 2][1] > self.heap[poi][1]: self.pos[poi], self.pos[(poi - 1) // 2] = ( self.pos[(poi - 1) // 2], self.pos[poi], ) self.swap(poi, (poi - 1) // 2) poi = (poi - 1) // 2 def is_empty(self): return True if self.heap_size == 0 else False def is_in_heap(self, v): if v in self.pos: if self.pos.index(v) < self.heap_size: return True return False

Checking if Min Heap PQ is working as expected

In [2]:

heap = MinHeapPriorityQueue()

heap = MinHeapPriorityQueue()

In [3]:

heap.insert_min_heap(0, 10)  # 0
heap.insert_min_heap(1, 7)  # 1
heap.insert_min_heap(2, 4)  # 2
heap.insert_min_heap(3, 5)  # 3
heap.insert_min_heap(4, 3)  # 4

heap.insert_min_heap(0, 10) # 0 heap.insert_min_heap(1, 7) # 1 heap.insert_min_heap(2, 4) # 2 heap.insert_min_heap(3, 5) # 3 heap.insert_min_heap(4, 3) # 4

In [4]:

heap.heap

heap.heap

Out[4]:

[[4, 3], [2, 4], [1, 7], [0, 10], [3, 5]]

In [5]:

heap.is_empty()

heap.is_empty()

Out[5]:

False

In [6]:

heap.is_in_heap(4)

heap.is_in_heap(4)

Out[6]:

True

In [7]:

heap.get_min_root()

heap.get_min_root()

Out[7]:

[4, 3]

In [8]:

heap.heap

heap.heap

Out[8]:

[[2, 4], [1, 7], [0, 10], [3, 5]]

In [9]:

heap.pos

heap.pos

Out[9]:

[2, 1, 0, 3]

In [10]:

heap.is_in_heap(4)

heap.is_in_heap(4)

Out[10]:

False

In [11]:

heap.heap_size

heap.heap_size

Out[11]:

4

Adjacency List representation of graph

In [12]:

from collections import defaultdict


class Graph:
    def __init__(self, V):
        self.V = V
        self.graph = defaultdict(list)

    # Adds an edge to an undirected graph
    def addEdge(self, src, dest, weight):

        # Add an edge from src to dest.  A new node is
        # added to the adjacency list of src. The node
        # is added at the beginning. The first element of
        # the node has the destination and the second
        # elements has the weight
        newNode = [dest, weight]
        self.graph[src].insert(0, newNode)

        # Since graph is undirected, add an edge from
        # dest to src also
        newNode = [src, weight]
        self.graph[dest].insert(0, newNode)

    # The main function that prints the Minimum
    # Spanning Tree(MST) using the Prim's Algorithm.
    # It is a O(ELogV) function

from collections import defaultdict class Graph: def __init__(self, V): self.V = V self.graph = defaultdict(list) # Adds an edge to an undirected graph def addEdge(self, src, dest, weight): # Add an edge from src to dest. A new node is # added to the adjacency list of src. The node # is added at the beginning. The first element of # the node has the destination and the second # elements has the weight newNode = [dest, weight] self.graph[src].insert(0, newNode) # Since graph is undirected, add an edge from # dest to src also newNode = [src, weight] self.graph[dest].insert(0, newNode) # The main function that prints the Minimum # Spanning Tree(MST) using the Prim's Algorithm. # It is a O(ELogV) function

In [13]:

graph = Graph(9)
graph.addEdge(0, 1, 4)
graph.addEdge(0, 7, 8)
graph.addEdge(1, 2, 8)
graph.addEdge(1, 7, 11)
graph.addEdge(2, 3, 7)
graph.addEdge(2, 8, 2)
graph.addEdge(2, 5, 4)
graph.addEdge(3, 4, 9)
graph.addEdge(3, 5, 14)
graph.addEdge(4, 5, 10)
graph.addEdge(5, 6, 2)
graph.addEdge(6, 7, 1)
graph.addEdge(6, 8, 6)
graph.addEdge(7, 8, 7)

graph = Graph(9) graph.addEdge(0, 1, 4) graph.addEdge(0, 7, 8) graph.addEdge(1, 2, 8) graph.addEdge(1, 7, 11) graph.addEdge(2, 3, 7) graph.addEdge(2, 8, 2) graph.addEdge(2, 5, 4) graph.addEdge(3, 4, 9) graph.addEdge(3, 5, 14) graph.addEdge(4, 5, 10) graph.addEdge(5, 6, 2) graph.addEdge(6, 7, 1) graph.addEdge(6, 8, 6) graph.addEdge(7, 8, 7)

In [14]:

graph.graph

graph.graph

Out[14]:

defaultdict(list,
            {0: [[7, 8], [1, 4]],
             1: [[7, 11], [2, 8], [0, 4]],
             7: [[8, 7], [6, 1], [1, 11], [0, 8]],
             2: [[5, 4], [8, 2], [3, 7], [1, 8]],
             3: [[5, 14], [4, 9], [2, 7]],
             8: [[7, 7], [6, 6], [2, 2]],
             5: [[6, 2], [4, 10], [3, 14], [2, 4]],
             4: [[5, 10], [3, 9]],
             6: [[8, 6], [7, 1], [5, 2]]})

In [15]:

def printArr(parent, n):
    for i in range(1, n):
        print("% d - % d" % (parent[i], i))

def printArr(parent, n): for i in range(1, n): print("% d - % d" % (parent[i], i))

In [16]:

def prims(graph, num_vertices):

    key = []
    parent = []

    heap = MinHeapPriorityQueue()

    for v in range(num_vertices):
        parent.append(-1)
        key.append(10000)
        heap.heap.append([v, key[v]])
        heap.pos.append(v)

    heap.pos[0] = 0
    key[0] = 0

    heap.decrease_key(0, key[0])

    heap.heap_size = num_vertices

    print(heap.pos)

    while heap.is_empty() == False:
        node = heap.get_min_root()
        u = node[0]

        for pcrawl in graph[u]:
            v = pcrawl[0]
            if heap.is_in_heap(v) and pcrawl[1] < key[v]:
                key[v] = pcrawl[1]
                parent[v] = u

                heap.decrease_key(v, key[v])

    printArr(parent, num_vertices)

def prims(graph, num_vertices): key = [] parent = [] heap = MinHeapPriorityQueue() for v in range(num_vertices): parent.append(-1) key.append(10000) heap.heap.append([v, key[v]]) heap.pos.append(v) heap.pos[0] = 0 key[0] = 0 heap.decrease_key(0, key[0]) heap.heap_size = num_vertices print(heap.pos) while heap.is_empty() == False: node = heap.get_min_root() u = node[0] for pcrawl in graph[u]: v = pcrawl[0] if heap.is_in_heap(v) and pcrawl[1] < key[v]: key[v] = pcrawl[1] parent[v] = u heap.decrease_key(v, key[v]) printArr(parent, num_vertices)

In [17]:

prims(graph.graph, num_vertices=9)

prims(graph.graph, num_vertices=9)

[0, 1, 2, 3, 4, 5, 6, 7, 8]
 0 -  1
 5 -  2
 2 -  3
 3 -  4
 6 -  5
 7 -  6
 0 -  7
 2 -  8

In [ ]: