Kruskal module¶

Kruskal’s algorithm for a minimum spanning tree. Using the idea of a forest, we pick minimum weight edges from the graph and use them to connect components. Each component is a tree itself and once we have connected every component our forest as grown into a beautiful spanning tree.

Algorithm 5.4.2 on page 85

Kruskal.comp_rep(comp_ptr, u)¶

Find the component representative for the input vertex

Parameters

comp_ptrlist

The list of component pointers

uint

The vertex of interest

Returns

int :

The component representative of the component u is a part of

Kruskal.kruskal(G)¶

Perform Kruskal’s minimum spanning tree algorithm on the graph

Parameters

Gnx.Graph

Returns

nx.Graph

The minimum spanning tree of the graph

Kruskal.merge(comp_ptr, u_rep, v_rep)¶

Merge the smaller component into the larger one

Parameters

comp_ptrList of int

The list of component pointers

u_repint

The component representative for the first component

v_repint

The component representative for the first component