Giải thuật đầu tiên để tìm cây bao trùm nỏnhỏ nhất do nhà khoa học người Séc [[Otakar Borůvka]] nghĩ ra vào năm 1926 (xem [[Giải thuật của Borůvka]]). Mục đích của ông là nghĩ ra cách phủ mạng điện hiệu quả tại [[Morava|Moravia]]. Hiện nay có hai giải thuật thường được sử dụng, [[Giải thuật của Prim]] và [[Giải thuật của Kruskal]]. Cả ba giải thuật này đều thuộc dạng [[giải thuật tham lam]] chạy với thời gian đa thức, vì vậy bài toán tìm cây bao trùm nhỏ nhất là dạng '''[[FP (độ phức tạp)|FP]]''', và các [[bài toán ra quyết định]] liên quan như xác định xem một cạnh cụ thể có thuộc MST hay không hoặc xác định xem tổng trọng số tối thiểu có vượt quá một giá trị nào đó hay không, là thuộc dạng '''[[P (độ phức tạp)|P]]'''. Một giải thuật tham lam khác không được phổ biến bằng đó là [[giải thuật ngược-xóa]], là dạng đảo ngược của giải thuật của Kruskal.
Nếu trọng số của cạnh là số nguyên, thì giải thuật các đơn định giải được bài toán với ''O''(''m'' + ''n'') phép tính nguyên.<ref>{{chú thích
