Thuật toán Borůvka

Định nghĩa một "thành phần" là một đỉnh hay một tập hợp liên thông các đỉnh, sau đây là mã giả của thuật toán Borůvka (không mất tính tổng quát giả sử các cạnh đồ thị G có trọng số khác nhau):

 1 Khởi tạo một tập rỗng T 2 Chừng nào các đỉnh của G vẫn chưa liên thông bởi tập cạnh trong T: 3   Khởi tạo một tập rỗng E 4   Với mỗi thành phần: 5     Thêm cạnh nhỏ nhất nối S với một đỉnh không thuộc S vào E 6   Thêm tập hợp E vào T. 7 Tập hợp T là một cây bao trùm nhỏ nhất của G.

Có thể chứng minh vòng lặp ngoài của thuật toán Borůvka thực hiện O(log |V|) lần, và mỗi lần mất thời gian ${\displaystyle O(|E|)}$ nên thuật toán chạy trong thời gian O(|E|log |V|), trong đó E là tập hợp cạnh, và V là tập hợp đỉnh G. Trong đồ thị phẳng, và tổng quát hơn là các lớp đồ thị đóng bởi toán tử đồ thị con đồng phôi, có thể làm thuật toán chạy trong thời gian tuyến tính, bằng cách loại đi tất cả các cạnh ngoại trừ cạnh nhỏ nhất giữa hai thành phần.^[7]

Một vài thuật toán khác cho bài toán này bao gồm thuật toán Prim (thực ra được tìm ra đầu tiên bởi Vojtěch Jarník) và thuật toán Kruskal. Một thuật toán ngẫu nhiên một phần dựa trên thuật toán Borůvka tìm ra bởi Karger, Klein, và Tarjan chạy trong thời gian kì vọng ${\displaystyle O(|E|)}$ . Thuật toán đơn định tốt nhất hiện nay cho cây bao trùm nhỏ nhất là của Bernard Chazelle cũng một phần dựa trên thuật toán Borůvka và chạy trong thời gian O(|E| α(|V|)), trong đó α là hàm ngược của hàm Ackermann. Các thuật toán này kết hợp các bước của thuật toán Borůvka để giảm số thành phần liên thông, với một bước khác để giảm số cạnh giữa các thành phần.