minimum cost spanning tree
Notes from lecture: minimum cost spanning trees.
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:
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: