Giới thiệu

Chào mừng bạn đến với khóa học cuối cùng trong loạt bài Thuật toán đồ thị! Giống như Kruskal, thuật toán Prim xây dựng một cây khung nhỏ nhất: tập hợp các cạnh có tổng trọng số thấp nhất, kết nối mọi đỉnh mà không tạo thành chu trình. Hai thuật toán tìm ra cùng một đáp án theo những cách khác nhau.

Prim mở rộng cây từ một đỉnh bắt đầu. Ở mỗi bước, thuật toán thêm cạnh có trọng số thấp nhất nối cây với một đỉnh chưa thuộc cây.

Đồ thị vô hướng và có trọng số, được cho dưới dạ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, ...] biểu diễn cạnh vô hướng u - v có trọng số w. Ta bắt đầu từ đỉnh 0.

Cùng hoàn thành loạt bài này nào!