MST Introduction 🎯

Welcome to a fascinating journey into the world of Data Structures and Algorithms! Today, we'll delve into one of the most powerful techniques for solving complex graph problems: the Minimum Spanning Tree (MST).

What is Minimum Spanning Tree (MST) 📝?

An MST is a tree that spans all the vertices (or nodes) of a connected graph, without any cycles, and has the minimum possible total edge weight.

Why is it important?

It helps in finding the shortest path between any two vertices in a graph.
It's used in network design, computing, and telecommunication to minimize the cost of laying cables or wires.

Real-world examples 💡

Think of a power grid where each node represents a city and edges represent power lines between them. The goal is to lay power lines in the most efficient way (minimizing the total cost) while ensuring every city is connected. This is exactly what MST helps us do!

Algorithms for finding MST 🎯

Prim's Algorithm: This algorithm builds the MST incrementally by adding vertices (cities) and their minimum-weight edges (power lines) one by one.
Kruskal's Algorithm: This algorithm sorts all edges in the graph by their weight and then adds them to the MST one by one, ensuring no cycles are formed.

Prerequisites 📝

Understanding of Graph Data Structures
Basic knowledge of Depth-First Search (DFS) and Union-Find algorithms

Code Examples ✅

Here are complete, working examples of both Prim's and Kruskal's algorithms in Python:

Prim's Algorithm

python

import heapq

def min_spanning_tree(graph, start_vertex):
    shortest_tree = {}
    unvisited = set(graph.keys())
    priority_queue = [(graph[start_vertex][start_vertex], start_vertex)]

    while unvisited:
        _, current_vertex = heapq.heappop(priority_queue)
        unvisited.remove(current_vertex)

        shortest_tree[current_vertex] = {current_vertex}

        for neighbor, weight in graph[current_vertex].items():
            if neighbor in unvisited:
                shortest_tree[neighbor].update(shortest_tree[current_vertex])
                heapq.heappush(priority_queue, (weight, neighbor))

    return shortest_tree

Kruskal's Algorithm

python

class UnionFind:
    def __init__(self, vertices):
        self.parents = {}
        self.ranks = {}
        for vertex in vertices:
            self.parents[vertex] = vertex
            self.ranks[vertex] = 0

    def find(self, vertex):
        if vertex != self.parents[vertex]:
            self.parents[vertex] = self.find(self.parents[vertex])
        return self.parents[vertex]

    def union(self, vertex1, vertex2):
        root1 = self.find(vertex1)
        root2 = self.find(vertex2)

        if root1 != root2:
            if self.ranks[root1] < self.ranks[root2]:
                self.parents[root1] = root2
            elif self.ranks[root2] < self.ranks[root1]:
                self.parents[root2] = root1
            else:
                self.parents[root2] = root1
                self.ranks[root1] += 1

def min_spanning_tree(graph):
    uf = UnionFind(graph.keys())
    edges = []

    for vertex1 in graph.keys():
        for vertex2, weight in graph[vertex1].items():
            edges.append((weight, vertex1, vertex2))

    edges.sort()

    mst = []
    for weight, vertex1, vertex2 in edges:
        if uf.find(vertex1) != uf.find(vertex2):
            mst.append((vertex1, vertex2, weight))
            uf.union(vertex1, vertex2)

    return mst

Quiz 💡

Happy learning! 🎓