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 the start_node.
  • edges: A priority queue (min heap) initialized with edges from the start_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 the visited set, and the edge is added to the mst.
  • 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.

• 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.