Module dsa.prim

Functions

def is_equal_set(visited: set, edges: list) ‑> bool

Deprecated This function is not necessary. Checks if the set of visited vertices is equal to the set of vertices in the edges list.

Args

visited : set

A set of visited vertices.

edges : list

A list of edges represented as tuples of vertices.

Returns

bool

True if visited set is equal to the set of vertices in edges, False otherwise.

def mst_weight(graph) ‑> int

Returns the total weight of a graph given a starting vertex

Args

graph

The graph to find the total edge weight of.

Returns

int

The total weight of the graph.

def prims_mst(graph, start: str, mst_graph=None) ‑> AdjacencyListWeightedGraph

Returns an MST given a graph and starting vertex

Args

graph

the graph to search an MST from

start : string

the starting vertex label

mst_graph

an empty graph object to output the MST in to (can be either an AdjacencyListWeightedGraph or AdjacencyMatrixWeightedGraph)

Returns

AdjacencyListWeightedGraph

the MST of the graph