Thuật toán Kruskal

Thuật toán Kruskal và Prim - Tìm Cây Khung Nhỏ Nhất (Minimum Spanning Tree)

1. Giới thiệu Trong lý thuyết đồ thị, bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) là một trong những bài toán cơ bản và quan trọng nhất. Bài toán này có nhiều ứng dụng thực tế trong các lĩnh vực như thiết kế mạng, quy

Cây khung nhỏ nhất

Cây Khung Nhỏ Nhất (Minimum Spanning Tree - MST) là gì?

TLDR: MST là cây khung có tổng trọng số nhỏ nhất, dùng để kết nối tất cả các đỉnh với chi phí tối thiểu. 3 thuật toán chính: Kruskal (sắp xếp cạnh), Prim (mở rộng từ đỉnh), Boruvka (hợp nhất rừng cây). Giới thiệu về Cây Khung Cây khung (spanning