Minimum Spanning Tree in a Weighted Graph
December 24, 2023
Problem #
Given a weighted undirected graph, find a minimum spanning tree that connects all nodes while minimizing the total weight of the edges
Solution #
Below is the complete Python code that finds a minimum spanning tree (MST) for a given weighted undirected graph using a variant of Prim’s algorithm:
import heapq
def minimum_spanning_tree(graph):
# Assuming the graph is represented as an adjacency list where each entry is
# a tuple of (node, weight), and graph is a dictionary
# Initialize variables
start_node = next(iter(graph)) # Starting from the first node in the graph
mst = set() # To store the edges of the Minimum Spanning Tree
visited = set([start_node])
edges = [(weight, start_node, to) for to, weight in graph[start_node]]
heapq.heapify(edges) # Convert list of edges to a heap for efficient minimum edge extraction
while edges:
weight, from_node, to_node = heapq.heappop(edges)
if to_node not in visited:
visited.add(to_node)
mst.add((from_node, to_node, weight))
for next_node, next_weight in graph[to_node]:
if next_node not in visited:
heapq.heappush(edges, (next_weight, to_node, next_node))
return mst
# Example usage
graph = {
'A': [('B', 1), ('C', 3)],
'B': [('A', 1), ('C', 1), ('D', 3)],
'C': [('A', 3), ('B', 1), ('D', 1)],
'D': [('B', 3), ('C', 1)]
}
mst = minimum_spanning_tree(graph)
print(mst)
This code will output a set of tuples, where each tuple represents an edge in the minimum spanning tree. Each edge is denoted by its start node, end node, and weight. In the provided example, the graph is defined with nodes ‘A’, ‘B’, ‘C’, and ‘D’, and the function minimum_spanning_tree
computes the MST of this graph.
Solution analysis #
The Python code provided solves the problem of finding a minimum spanning tree (MST) for a given weighted undirected graph. The algorithm used here is a variant of Prim’s algorithm, which builds the minimum spanning tree by adding edges one at a time from the set of edges that connect the tree to vertices not yet in the tree, selecting the smallest weight edge at each step.
Here’s a breakdown of the code:
Function minimum_spanning_tree
#

Input:
graph
, a dictionary representing a weighted undirected graph. Each key is a node, and the value is a list of tuples(neighbor, weight)
representing an edge to a neighbor and its weight. 
Initialization:
start_node
: The algorithm starts from an arbitrary node in the graph.mst
: A set to store the edges included in the minimum spanning tree.visited
: A set to track visited nodes, initialized with thestart_node
.edges
: A priority queue (min heap) initialized with edges from thestart_node
. Each edge is a tuple(weight, from_node, to_node)
.

Algorithm:
 The algorithm repeatedly extracts the edge with the smallest weight from the priority queue
edges
.  If the
to_node
of this edge has not been visited, it is added to thevisited
set, and the edge is added to themst
.  Then, it adds to the priority queue all edges from the
to_node
to its unvisited neighbors.  This process repeats until there are no more edges in the priority queue.
 The algorithm repeatedly extracts the edge with the smallest weight from the priority queue

Output: The set
mst
represents the minimum spanning tree as a set of edges(from_node, to_node, weight)
.
Example Usage #
 The graph is defined with nodes ‘A’, ‘B’, ‘C’, and ‘D’, and their corresponding weighted edges.
 The
minimum_spanning_tree
function is called with this graph, and it returns a set of edges representing the MST.  The output
{('A', 'B', 1), ('B', 'C', 1), ('C', 'D', 1)}
represents the minimum spanning tree of the given graph with the total minimum weight.
This code is efficient for finding a minimum spanning tree in a weighted undirected graph and is particularly useful in network design, circuit design, and other fields where a minimal connecting structure is required.