[👨‍💻🇻🇳] Tìm cây khung nhỏ nhất

Ngoài thuật toán Prim, Thuật toán Kruskal cũng là thuật toán cổ điển để giải bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree) cho đồ thị vô hướng có trọng số. Trong bài viết này chúng ta cùng xem ý tưởng cơ bản của Thuật toán Kruskal.

Cây khung (spanning tree) của một đồ thị là một đồ thị con liên thông không có chu trình đi qua tất cả các đỉnh. Một đồ thị sẽ có nhiều cây khung và bài toán của chúng ta là phải tìm ra cây khung nhỏ nhất.

Ý tưởng của Thuật toán Kruskal khá đơn giản: Sắp xếp các cạnh từ bé đến lớn theo trọng số. Lần lượt chọn các cạnh theo thứ tự từ bé đến lớn trong danh sách sao cho không tạo thành chu trình. Thuật toán sẽ dừng lại khi đã có đủ $V-1$ cạnh trong cây khung (với $V$ là số lượng đỉnh của đồ thị).

Để minh họa cho thuật toán, mình sẽ dùng đồ thị $G$ và đi từng bước của thuật toán:

Đồ thị $G$

Trong danh sách các cạnh của $G$, ta lấy ra cạnh 2-4 nhỏ nhất.

Cạnh này không tạo chu trình nên có thể đưa vào cây khung và xét cạnh 1-4.

Đưa 1-4 vào cây khung, xét cạnh 2-5.

Đưa 2-5 vào cây khung, xét cạnh 6-8.

Đưa 6-8 vào cây khung, xét cạnh 6-7.

Đưa 6-7 vào cây khung, xét cạnh 5-6.

Đưa 5-6 vào cây khung, xét cạnh 0-2.

Đưa 0-2 vào cây khung, xét cạnh 5-7. Cạnh 5-7 tạo thành chu trình, vì vậy không được đưa vào cây khung. Ta xét tiếp cạnh 7-8, cũng không được đưa vào cây khung do tạo thành chu trình. Xét cạnh 0-3.

Đưa 0-3 vào cây khung. Thuật toán kết thúc vì đã đủ $V-1$ cạnh.