9. Minimum Spanning Tree using Kruskals Algorithm

MST using Kruskal's Algorithm¶

References:¶

how to represent weighted graphs

1. https://codereview.stackexchange.com/questions/163414/adjacency-list-graph-representation-on-python
2. https://stackoverflow.com/questions/13547133/adjacency-list-and-adjacency-matrix-in-python
3. Unexplored but looks promising: https://www.bogotobogo.com/python/python_graph_data_structures.php

In [1]:

from utils.graph import WeightedGraphAdjList as Graph
from utils.graph_properties import WeightedGraphPropertiesAdjList as gp
from utils.disjoint_set import DisjointSetNaive as dso

from utils.graph import WeightedGraphAdjList as Graph from utils.graph_properties import WeightedGraphPropertiesAdjList as gp from utils.disjoint_set import DisjointSetNaive as dso

In [2]:

def kruskal_MST(graph):

    result = []
    i = 0
    e = 0

    sorted_graph = sorted(graph, key=lambda item: item[2])

    num_vertices = gp.num_vertices_weighted(graph)
    universe = list(range(num_vertices))
    unf = dso()
    unf.make_set(universe)

    # for MST the number of nodes will be 1-#edges in graph
    while e < num_vertices - 1:
        u, v, w = sorted_graph[i]
        i += 1

        x = unf.find(u)
        y = unf.find(v)

        if x != y:
            result.append([u, v, w])
            e += 1
            unf.union(x, y)

    minimum_cost = 0

    for u, v, w in result:
        minimum_cost += w
        print(f"{u} -- {v} = {w}")

    print(f"MST Cost: {minimum_cost}")

def kruskal_MST(graph): result = [] i = 0 e = 0 sorted_graph = sorted(graph, key=lambda item: item[2]) num_vertices = gp.num_vertices_weighted(graph) universe = list(range(num_vertices)) unf = dso() unf.make_set(universe) # for MST the number of nodes will be 1-#edges in graph while e < num_vertices - 1: u, v, w = sorted_graph[i] i += 1 x = unf.find(u) y = unf.find(v) if x != y: result.append([u, v, w]) e += 1 unf.union(x, y) minimum_cost = 0 for u, v, w in result: minimum_cost += w print(f"{u} -- {v} = {w}") print(f"MST Cost: {minimum_cost}")

In [3]:

g = Graph()
g.insert_weighted_node(0, 1, 10)
g.insert_weighted_node(0, 2, 6)
g.insert_weighted_node(0, 3, 5)
g.insert_weighted_node(1, 3, 15)
g.insert_weighted_node(2, 3, 4)

g = Graph() g.insert_weighted_node(0, 1, 10) g.insert_weighted_node(0, 2, 6) g.insert_weighted_node(0, 3, 5) g.insert_weighted_node(1, 3, 15) g.insert_weighted_node(2, 3, 4)

In [4]:

kruskal_MST(g.graph)

kruskal_MST(g.graph)

2 -- 3 = 4
0 -- 3 = 5
0 -- 1 = 10
MST Cost: 19