Giới thiệu

Chào mừng bạn quay lại với loạt bài Thuật toán đồ thị! Cây khung nhỏ nhất (MST) kết nối mọi đỉnh của một đồ thị có trọng số bằng cách dùng tổng trọng số cạnh nhỏ nhất có thể, không tạo chu trình nào.

Thuật toán Kruskal xây dựng cây khung nhỏ nhất theo cách tham lam: thuật toán sắp xếp các cạnh từ nhẹ nhất đến nặng nhất rồi thêm từng cạnh, miễn là cạnh đó không tạo chu trình. Bí quyết để phát hiện chu trình nhanh là dùng một cấu trúc dữ liệu gọi là hợp nhất-tìm kiếm (union-find), còn được gọi là tập hợp rời nhau.

Đồ thị vô hướng có trọng số được biểu diễn bằng n (các đỉnh từ 0 đến n - 1) và edges, một mảng phẳng gồm các bộ ba [u0, v0, w0, ...], mỗi bộ biểu diễn một cạnh vô hướng u - v có trọng số w.

Bắt đầu nhé!