this page ⟩ lc notes ⟩ collections ⟩ home

Kruskal’s algorithm for Minimum spanning tree

Kruskal’s algorithm is as follows.

  • Go in order of lowest to highest weighted edges.
  • Add edge to the graph if it doesn’t create a cycle.
@dataclass
class Edge:
    u: int
    v: int
    w: float

def kruskal_mst(num_edges: int, edges: List[Edge]) -> Tuple[List[Edge], float]:
    edges.sort(key=lambda x: x.w)
    dsu = DisjointSetUnion(num_edges)
    mst = []
    total_weight = 0

    for edge in edges:
        if dsu.find(edge.u) != dsu.find(edge.v):
            dsu.union(edge.u, edge.v) 
            mst.append(edge)
            total_weight += edge.w
            
    return mst, total_weight
  • Time Complexity: $O(m \log m + n + m) = O(m \log n)$
    • $O(m \log m)$ for sorting all edges
    • $O(n)$ for make set on each edges
    • $O(m)$ for find and union on all nodes in edges
  • Space Complexity: Extra space to maintaint the DSU datastructure ~ $O(n)$



tags: #mst