Minimum Spanning Tree (MST)

Question

The Minimum Spanning Tree (MST) of a graph is a subset of its edges that connects all vertices together, without forming any cycles, and with the minimum possible total edge weight. In other words, it's the cheapest possible way to connect all the nodes together without any loops.

To clarify with an example, consider a network of cities connected by roads with different distances. The MST would be the smallest set of roads that connect all cities together, while minimizing the total distance.

A graph can have multiple MSTs, but they will all have the same total weight. Algorithms like Kruskal's and Prim's are commonly used to find an MST of a given weighted, undirected graph.

In the context of the assignment, you would implement Kruskal's algorithm to find an MST of a given graph. The output would be a list of edges that form the MST, ideally with the smallest total edge weight.

Objective
You're given a weighted, undirected graph. Your task is to implement a function that finds the Minimum Spanning Tree (MST) of this graph using Kruskal's algorithm.
def kruskal_mst(graph: dict) -> list:
    pass

Inputs
The graph is a dictionary representing the weighted, undirected graph. The keys are the node names (strings), and the values are dictionaries containing adjacent nodes and the weights of the edges to them.

Output
Return a list of tuples, each representing an edge in the MST. Each tuple should contain the source node, destination node, and the edge weight.

Example
Given the following graph:
graph = {
    'NewYork': {'Chicago': 790, 'LosAngeles': 2445},
    'Chicago': {'NewYork': 790, 'LosAngeles': 1745, 'SanFrancisco': 1850},
    'LosAngeles': {'NewYork': 2445, 'Chicago': 1745, 'SanFrancisco': 350},
    'SanFrancisco': {'Chicago': 1850, 'LosAngeles': 350}
}
The function call kruskal_mst(graph) should return:
[('LosAngeles', 'SanFrancisco', 350), ('NewYork', 'Chicago', 790), ('Chicago', 'LosAngeles', 1745)]

Accepted Answer

# Implementing Kruskal's algorithm to find the Minimum Spanning Tree (MST)
def find_parent(node, parent):
    if parent[node] == node:
        return node
    parent[node] = find_parent(parent[node], parent)
    return parent[node]

def union_nodes(a, b, parent, rank):
    root_a = find_parent(a, parent)
    root_b = find_parent(b, parent)
    
    if root_a != root_b:
        if rank[root_a] > rank[root_b]:
            parent[root_b] = root_a
        else:
            parent[root_a] = root_b
            if rank[root_a] == rank[root_b]:
                rank[root_b] += 1

def kruskal_mst(graph):
    # Initialize parent and rank dictionaries for Union-Find
    parent = {node: node for node in graph}
    rank = {node: 0 for node in graph}
    
    # Create a list of all edges
    edges = []
    for node, neighbors in graph.items():
        for neighbor, weight in neighbors.items():
            edges.append((node, neighbor, weight))
    
    # Sort edges by weight
    edges.sort(key=lambda x: x[2])
    
    # Initialize the MST result list
    mst = []
    
    for edge in edges:
        node_a, node_b, weight = edge
        
        # Find the parents (roots) of the connected components for both nodes
        root_a = find_parent(node_a, parent)
        root_b = find_parent(node_b, parent)
        
        # If the nodes belong to different connected components, add the edge to the MST
        if root_a != root_b:
            mst.append((node_a, node_b, weight))
            union_nodes(node_a, node_b, parent, rank)
    
    return mst

# Test the function with a different example graph with city names
city_graph = {
    'NewYork': {'Chicago': 790, 'LosAngeles': 2445},
    'Chicago': {'NewYork': 790, 'LosAngeles': 1745, 'SanFrancisco': 1850},
    'LosAngeles': {'NewYork': 2445, 'Chicago': 1745, 'SanFrancisco': 350},
    'SanFrancisco': {'Chicago': 1850, 'LosAngeles': 350}
}

print(kruskal_mst(city_graph))  # Should return a MST with city names as nodes

Title	Category	Subcategory	Difficulty	Status
Dijkstra's Algorithm #1	Programming	Graphs	Hard	Example
Dijkstra's Algorithm #2	Programming	Graphs	Hard	Unlock
Find All Paths	Programming	Graphs	Hard	Unlock

The Interview Guide for Quants and Traders