diplomat.utils.graph_ops.min_spanning_tree

diplomat.utils.graph_ops.min_spanning_tree(graph: ndarray) → ndarray

Finds the minimum spanning tree of a graph encoded as an adjacency matrix. Algorithm is node-centric Prim’s, which guarantees a runtime of O(n^2) for all graphs, and is ideal for dense graphs.

Parameters:

graph – An adjacency matrix, assumes disconnected nodes have distance value of infinity.

Returns:

A new adjacency matrix, representing the minimum spanning tree covering the provided graph.