bhylu.com

Advertisements

DSA Kruskal's Algorithm

A minimum spanning tree connects an undirected connected graph using minimum total edge weight. On a disconnected graph, the corresponding result is a minimum spanning forest.

How it works

Kruskal considers edges in increasing weight order and uses disjoint sets to reject edges whose endpoints are already connected. The fixture contains an isolated hill, so no single spanning tree over every vertex exists. Negative edge weights are valid for this problem, unlike Dijkstra’s shortest-path precondition. A minimum forest is not a collection of shortest routes from a chosen source.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as kruskal.py and run python kruskal.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

kruskal.py
Try in playground

class DisjointSet:
    def __init__(self, vertices):
        vertices = list(vertices)
        if len(set(vertices)) != len(vertices):
            raise ValueError("Repeated vertex")
        self.parent = {vertex: vertex for vertex in vertices}
        self.size = {vertex: 1 for vertex in vertices}
        self.components = len(vertices)

    def find(self, vertex):
        if vertex not in self.parent:
            raise ValueError("Unknown vertex")
        while self.parent[vertex] != vertex:
            self.parent[vertex] = self.parent[self.parent[vertex]]
            vertex = self.parent[vertex]
        return vertex

    def union(self, first, second):
        first, second = self.find(first), self.find(second)
        if first == second:
            return False
        if self.size[first] < self.size[second]:
            first, second = second, first
        self.parent[second] = first
        self.size[first] += self.size[second]
        self.components -= 1
        return True

def validate_edges(vertices, edges):
    if len(set(vertices)) != len(vertices) or any(not isinstance(vertex, str) for vertex in vertices):
        raise ValueError("Unique string vertices required")
    known = set(vertices)
    for first, second, weight in edges:
        if first not in known or second not in known or type(weight) is not int:
            raise ValueError("Invalid undirected edge")

def kruskal(vertices, edges):
    validate_edges(vertices, edges)
    groups = DisjointSet(vertices)
    selected, total = [], 0
    for first, second, weight in sorted(edges, key=lambda edge: (edge[2], edge[0], edge[1])):
        if groups.union(first, second):
            selected.append((first, second, weight))
            total += weight
    return selected, total

vertices = ["gate", "oak", "pond", "shed", "hill"]
edges = [("gate", "oak", 4), ("gate", "pond", 1), ("pond", "oak", 2), ("oak", "shed", 1), ("pond", "shed", 7)]
selected, total = kruskal(vertices, edges)
print(len(selected), total)
print(len(vertices) - len(selected))

Expected result

3 4
2

Three selected edges connect the four reachable orchard locations for total cost four, while hill remains its own component. Equal-cost alternatives can be valid even when the exact selected edges differ. The review compares total cost and forest invariants with exhaustive small cases.

Time, space and assumptions

Sorting takes O(E log E), followed by near-linear disjoint-set work. Structure/output storage is O(V+E), including the sorted edge list created by this implementation.

Consult the Python 3.12 standard-library reference for container and language contracts; an example result is not a proof of every possible input or real-world performance.

Advertisements