Skip to main content
This module implements Prim’s algorithm for finding the minimum spanning tree (MST) of a weighted graph.

​
Functions

​
prims_mst

Computes the minimum spanning tree of a weighted graph using Prim’s algorithm. 
from dsa.prim import prims_mst

mst = prims_mst(graph, start, mst_graph=None)
​
graph
AdjacencyListWeightedGraph | AdjacencyMatrixWeightedGraph
required
The weighted graph to find the MST from. Can be either an AdjacencyListWeightedGraph or AdjacencyMatrixWeightedGraph
​
start
str
required
The starting vertex label for building the MST
​
mst_graph
AdjacencyListWeightedGraph
default:"None"
An empty graph object to output the MST into. If None, a new AdjacencyListWeightedGraph is created
​
mst
AdjacencyListWeightedGraph
The minimum spanning tree of the input graph
from dsa.graph import AdjacencyListWeightedGraph
from dsa.prim import prims_mst

# Create a weighted graph
graph = AdjacencyListWeightedGraph()
graph.add_edge("A", "B", 4)
graph.add_edge("A", "C", 2)
graph.add_edge("B", "C", 1)
graph.add_edge("B", "D", 5)
graph.add_edge("C", "D", 8)
graph.add_edge("C", "E", 10)
graph.add_edge("D", "E", 2)

# Find minimum spanning tree
mst = prims_mst(graph, "A")
print(list(mst.edges()))  # MST edges with weights

​
mst_weight

Calculates the total weight of all edges in a graph (typically used for MST graphs). 
from dsa.prim import mst_weight

total = mst_weight(graph)
​
graph
Graph
required
The graph to calculate the total edge weight of (must have an edges() method)
​
total
int
The total weight of all edges in the graph
from dsa.graph import AdjacencyListWeightedGraph
from dsa.prim import prims_mst, mst_weight

# Create a weighted graph
graph = AdjacencyListWeightedGraph()
graph.add_edge("A", "B", 4)
graph.add_edge("A", "C", 2)
graph.add_edge("B", "C", 1)
graph.add_edge("B", "D", 5)
graph.add_edge("C", "D", 8)

# Find MST and calculate its total weight
mst = prims_mst(graph, "A")
total_weight = mst_weight(mst)
print(f"MST total weight: {total_weight}")
How Prim’s Algorithm Works:
  1. Start with a single vertex and mark it as visited
  2. Add all edges from the visited vertex to the priority queue
  3. Pop the edge with minimum weight from the priority queue
  4. If the destination vertex hasn’t been visited:
    • Add the edge to the MST
    • Mark the destination as visited
    • Add all edges from the new vertex to the priority queue
  5. Repeat steps 3-4 until all vertices are visited
Time Complexity: O((V + E) log V) where V is vertices and E is edgesSpace Complexity: O(V) for the visited set and priority queueNote: The resulting MST is unique if all edge weights are distinct. If there are edges with equal weights, multiple valid MSTs may exist.

Build docs developers (and LLMs) love

Get started for freeTalk to us