# minimum cost spanning tree

🏠

Notes from lecture: minimum cost spanning trees.

Our graph can be discribed as $G = (V, E)$ with verts $V = \{1,2,3,4\}$ and edges $E = \{ (1,2), (2,3), (3,4), (4,1) \}$.

Since $|V| = n = 6$, a minimum cost spanning tree of G would have $|E| = |V|-1 = 5$

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
11
12     def PrimsMST(self):
13         q = [[0, Node(self.source)]]
15         mst_cost = 0
17             cost, node = heapq.heappop(q)
19                 mst_cost += cost
21                 print(f"Added Node : {node.numid}, cost now : {mst_cost}")
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 = [E(2, 28), E(6, 10)]
37 g = [E(7, 14), E(3, 16), E(1, 28)]
38 g = [E(4, 12), E(2, 16)]
39 g = [E(5, 22), E(7, 18), E(3, 12)]
40 g = [E(4, 22), E(7, 24), E(6, 25)]
41 g = [E(5, 25), E(1, 10)]
42 g = [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")