[Bài toán] Xây dựng đường sắt

Bài toán: Bộ xây dựng đang có kế hoạch xây dựng hệ thống đường sắt nối liền các thành phố với nhau, sao cho chỉ có duy nhất 1 tuyến đường sắt nối liền hai thành phố bất kỳ. Sau khi nhiên cứu tính toán chi phí xây dựng các tuyến đường sắt nối liền các thành phố, bộ xây dựng thu...

[Thuật toán] Prim - Tìm cây khung nhỏ nhất

 Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị có số cạnh khoảng m=n (n-1)/2. Trong những tình huống như vậy, thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn được mang tên là người láng giềng gần nhất. Trong thuật toán này, bắt đầu tại một đỉnh tuỳ...

[Thuật toán] Kruskal - Tìm cây khung nhỏ nhất

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây. Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau: 1.  Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh; 2.  Xuất phát từ tập cạnh T=φ, ở...

[Thuật toán] Kruskal - Tìm cây khung nhỏ nhất

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây. Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau: 1.  Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh; 2.  Xuất phát từ tập cạnh T=φ, ở...