minimum cost spanning tree

← 🏠

Notes from lecture: minimum cost spanning trees.

D 1 1 2 2 1->2 3 3 2->3 6 6 6->1 4 4 3->4 5 5 5->6 4->5

Our graph can be discribed as with verts and edges .

Since , a minimum cost spanning tree of G would have

The minimum cost spanning tree is a subset of E. In fact here's a definition:




D 1 1 2 2 1->2 3 3 2->3 6 6 4 4 3->4 5 5 5->6 4->5

Credit for this implementation: algo tree.

 1 from dataclasses import dataclass
 2 from collections import defaultdict as dd
 3 from collections import namedtuple
 4 import heapq
 5 
 6 
 7 @dataclass
 8 class Graph:
 9     source: int
10     adjlist: dict
11 
12     def PrimsMST(self):
13         q = [[0, Node(self.source)]]
14         added = dd(bool)
15         mst_cost = 0
16         while q and len(added) <= len(self.adjlist):
17             cost, node = heapq.heappop(q)
18             if not added[node.numid]:
19                 mst_cost += cost
20                 added[node.numid] = True
21                 print(f"Added Node : {node.numid}, cost now : {mst_cost}")
22                 for item in self.adjlist[node.numid]:
23                     if not added[item.vert]:
24                         heapq.heappush(q, [item.cost, Node(item.vert)])
25         return mst_cost
26 
27 
28 @dataclass(eq=True)
29 class Node:
30     numid: int
31 
32 
33 E = namedtuple("WeightedEdge", "vert cost")
34 
35 g = {}
36 g[1] = [E(2, 28), E(6, 10)]
37 g[2] = [E(7, 14), E(3, 16), E(1, 28)]
38 g[3] = [E(4, 12), E(2, 16)]
39 g[4] = [E(5, 22), E(7, 18), E(3, 12)]
40 g[5] = [E(4, 22), E(7, 24), E(6, 25)]
41 g[6] = [E(5, 25), E(1, 10)]
42 g[7] = [E(5, 24), E(4, 18), E(2, 14)]
43 g1 = Graph(1, g)
44 cost = g1.PrimsMST()
45 print("Cost of the minimum spanning tree in graph 1 : " + str(cost) + "\n")

See also:

dataclass