dsap.graph.mst

module documentation

Provides MST_PrimJarnik and MST_Kruskal functions for computing the minimum spanning tree of a graph.

Function MST_Kruskal Compute a minimum spanning tree of a graph using Kruskal's algorithm.
Function MST_PrimJarnik Compute a minimum spanning tree of weighted graph g.
def MST_Kruskal(g):

Compute a minimum spanning tree of a graph using Kruskal's algorithm.

Return a list of edges that comprise the MST.

The elements of the graph's edges are assumed to be weights.

def MST_PrimJarnik(g):

Compute a minimum spanning tree of weighted graph g.

Return a list of edges that comprise the MST (in arbitrary order).