Cấu trúc dữ liệu và Giải thuật Bài 50: Cây khung nhỏ nhất (Minimum Spanning Tree) với thuật toán Prim và Kruskal.

Giả sử Hiếu được giao nhiệm vụ thiết kế hạ tầng mạng cáp quang kết nối toàn bộ hệ thống soát vé tự động (AFC) và cảm biến tín hiệu của 14 nhà ga Metro Line 1. Mục tiêu lúc này không phải là tìm đường truyền tin nhanh nhất từ Bến Thành đi Suối Tiên (đó là việc của Dijkstra), mà bài toán của bạn là: Làm sao để kết nối tất cả các ga lại với nhau thành một mạng liên thông với tổng chiều dài cáp quang là ngắn nhất?

Nếu bạn kéo cáp tạo thành một vòng tròn khép kín (chu trình), đó là sự lãng phí ngân sách vật tư. Cấu trúc mạng lưới tối ưu nhất để kết nối mọi điểm mà không dư thừa chính là Cây khung nhỏ nhất (Minimum Spanning Tree - MST).

1. Bản chất của Cây khung (Spanning Tree)

Khi bạn lấy một Đồ thị vô hướng, có liên thông (mọi đỉnh đều có đường đến nhau) và cắt bỏ đi các cạnh thừa thãi nhằm triệt tiêu toàn bộ chu trình, bạn sẽ thu được một cái Cây. Cây này gọi là "Cây khung" vì nó "chống đỡ" toàn bộ các đỉnh của đồ thị gốc.

Một Cây khung hợp lệ luôn sở hữu 3 đặc tính toán học bất di bất dịch:

1. Bao phủ toàn bộ $V$ đỉnh của đồ thị.

2. Sở hữu chính xác $V - 1$ cạnh.

3. Tuyệt đối không có chu trình (No cycles).

Một đồ thị có thể có rất nhiều Cây khung khác nhau. Cây khung nhỏ nhất (MST) là cây khung có tổng trọng số các cạnh là nhỏ nhất. Để tìm ra kiến trúc tối ưu này, Khoa học máy tính cung cấp hai thuật toán mang phong cách hoàn toàn trái ngược nhau: Kruskal (Góc nhìn toàn cục) và Prim (Góc nhìn cục bộ).

2. Thuật toán Kruskal (Góc nhìn Toàn cục)

Kruskal giải quyết bài toán bằng cách nhìn bao quát toàn bộ mạng lưới và áp dụng triết lý "nhặt nhạnh" những gì rẻ nhất.

Quy trình vận hành:

1. Phá vỡ đồ thị, gom toàn bộ các Cạnh ném vào một danh sách.

2. Sắp xếp danh sách Cạnh này theo trọng số tăng dần (Từ rẻ nhất đến đắt nhất).

3. Lần lượt bốc từng cạnh ra. Nếu cạnh đó nối 2 đỉnh chưa được kết nối (không tạo ra chu trình), ta giữ nó lại để xây MST.

4. Nếu cạnh đó tạo ra chu trình (tức là 2 đỉnh của nó đã được nối với nhau bởi một đường khác từ trước), ta vứt bỏ nó ngay lập tức.

5. Dừng lại khi đã nhặt đủ $V - 1$ cạnh.

Thuật toán Kruskal cực kỳ dễ hiểu, nhưng nó đòi hỏi một hệ thống "Radar" cực nhạy để phát hiện chu trình ở Bước 4. Hệ thống radar này chính là Cấu trúc dữ liệu Disjoint Set (Union-Find). Tốc độ của Kruskal chủ yếu phụ thuộc vào việc sắp xếp các cạnh, đạt $O(E \log E)$.

3. Thuật toán Prim (Góc nhìn Cục bộ)

Nếu Kruskal xây cây bằng cách nhặt các cạnh rời rạc rồi ghép lại, thì Prim lại xây cây bằng cách "nuôi lớn" một mạng lưới từ một hạt giống duy nhất, giống hệt cách nấm mốc lan rộng.

Quy trình vận hành:

1. Chọn bừa một Đỉnh bất kỳ làm điểm xuất phát (hạt giống). Đưa nó vào tập hợp "Đã kết nối" (MST Set).

2. Quét tất cả các cạnh nối từ tập hợp "Đã kết nối" ra thế giới bên ngoài (các đỉnh chưa được thăm).

3. Chọn cạnh có chi phí rẻ nhất và nối Đỉnh mới đó vào mạng lưới.

4. Lặp lại Bước 2 và 3 cho đến khi toàn bộ $V$ đỉnh đều bị mạng lưới nuốt chửng.

Sự khác biệt lớn nhất giữa Prim và Dijkstra nằm ở cách tính giá: Dijkstra cộng dồn khoảng cách từ điểm xuất phát, còn Prim chỉ quan tâm đến trọng số của chính cái Cạnh đó, không cộng dồn.

4. Triển khai thuật toán Prim bằng Golang

Bởi vì Prim luôn phải đi tìm "Cạnh rẻ nhất" trong số hàng tá cạnh đang mở rộng, chúng ta lại triệu hồi cỗ máy Min-Heap (Priority Queue) để đẩy hiệu năng lên $O((V + E) \log V)$.

Go

import "container/heap"

// Cấu trúc một Cạnh cho Priority Queue
type EdgeItem struct {
    To     string
    Weight int
}

// Thuật toán Prim tìm tổng chi phí Cây khung nhỏ nhất
func PrimMST(adjList map[string][]EdgeItem, startNode string) int {
    visited := make(map[string]bool)
    totalCost := 0
    edgesCount := 0

    // Khởi tạo Min-Heap
    pq := &MinHeap{} // Giả định MinHeap đã implement sort.Interface
    heap.Init(pq)

    // Bắt đầu từ hạt giống đầu tiên
    visited[startNode] = true
    
    // Đẩy toàn bộ các cạnh của hạt giống vào Heap
    for _, edge := range adjList[startNode] {
        heap.Push(pq, edge)
    }

    // Vòng lặp nuôi lớn mạng lưới
    for pq.Len() > 0 && edgesCount < len(adjList)-1 {
        // Rút cạnh rẻ nhất hiện tại ra khỏi Heap
        cheapestEdge := heap.Pop(pq).(EdgeItem)
        nextNode := cheapestEdge.To

        // Tránh tạo chu trình: Nếu đỉnh đích đã nằm trong mạng lưới rồi thì bỏ qua
        if visited[nextNode] {
            continue
        }

        // Chốt hạ: Kết nối đỉnh mới vào mạng lưới
        visited[nextNode] = true
        totalCost += cheapestEdge.Weight
        edgesCount++

        // Đẩy tiếp các cạnh của đỉnh mới vào Heap để mở rộng tầm nhìn
        for _, nextEdge := range adjList[nextNode] {
            if !visited[nextEdge.To] { // Chỉ đẩy những cạnh hướng ra vùng đất chưa khám phá
                heap.Push(pq, nextEdge)
            }
        }
    }

    return totalCost
}

5. Chọn Prim hay Kruskal trong Kiến trúc Vận hành?

Việc chọn thuật toán phụ thuộc vào cấu hình của Đồ thị (Mật độ kết nối):

• Dùng thuật toán Prim: Khi bạn đối mặt với Đồ thị dày đặc (Dense Graph), nơi số lượng Cạnh ($E$) tiến gần tới $V^2$. Prim kết hợp với Ma trận kề hoặc Min-Heap hoạt động càn lướt từ trong ra ngoài mà không cần phải tốn công sắp xếp hàng triệu cạnh ngay từ đầu.

• Dùng thuật toán Kruskal: Khi hệ thống là Đồ thị thưa (Sparse Graph), hoặc khi bạn có sẵn một danh sách các Cạnh đã được phân loại/lưu trữ trong Database rời rạc.

Cây khung nhỏ nhất giải quyết trọn vẹn bài toán hạ tầng vật lý. Nhưng như đã đề cập ở thuật toán Kruskal, để máy tính có thể phân biệt được hai nhóm mạng lưới có đang dính vào nhau hay không (phát hiện chu trình $O(1)$), chúng ta cần một cấu trúc dữ liệu sinh ra chỉ để quản lý các tập hợp rời rạc.