I. Giới thiệu chung

Bài toán cây khung là một trong những chủ đề quan trọng trong lĩnh vực Cấu trúc dữ liệu và Thuật toán. Cây khung nhỏ nhất (Minimum Spanning Tree - MST) đã được nghiên cứu từ lâu và có nhiều ứng dụng trong thực tế. Trong bài viết này, chúng ta sẽ cùng tìm hiểu về cây khung, cây khung nhỏ nhất, và các thuật toán phổ biến để giải quyết vấn đề này.

1. Cây khung là gì?

Cây khung của một đồ thị vô hướng G(V, E) gồm các đỉnh V và cạnh E là một tập hợp các cạnh của đồ thị thỏa mãn hai điều kiện chính:

• Tập hợp các cạnh này không chứa chu trình.
• Tập hợp này liên thông và chứa tất cả các đỉnh của đồ thị.

Nói cách khác, nếu đồ thị có n đỉnh thì cây khung sẽ có n-1 cạnh.

2. Cây khung nhỏ nhất (MST)

Trong một đồ thị có trọng số, cây khung nhỏ nhất là cây khung mà tổng trọng số các cạnh là nhỏ nhất. Điều này có nghĩa là chúng ta cần tìm một cây liên thông chứa tất cả các đỉnh với tổng trọng số cạnh thấp nhất.

Định nghĩa bài toán:

Cho một đồ thị vô hướng G có n đỉnh và m cạnh. Với một cây khung T của đồ thị, trọng số của cây T là tổng trọng số của các cạnh trong cây. Nhiệm vụ của chúng ta là xác định cây khung có trọng số nhỏ nhất.

Input:

• Dòng đầu tiên chứa hai số nguyên n,m: số đỉnh và số cạnh của đồ thị.
• Các dòng tiếp theo chứa ba số u,v,c để biểu diễn một cạnh nối hai đỉnh u và v có trọng số c.

Output:

• Nếu tìm được cây khung nhỏ nhất, in ra trọng số của MST và các cạnh của nó. Nếu không, in ra thông báo "Unconnected Graph".

3. Thuật toán Kruskal

1. Ý tưởng

Thuật toán Kruskal được phát minh bởi Joseph Kruskal vào năm 1956. Ý tưởng chính của thuật toán này là khởi tạo một cây khung rỗng và thêm các cạnh vào cây theo thứ tự tăng dần của trọng số. Cây chỉ được thêm cạnh nếu không tạo thành chu trình.

2. Cài đặt

Demo cài đặt thuật toán Kruskal được thực hiện bằng ngôn ngữ C++ và Python.

C++ Implementation:

// C++ code here

Python Implementation:

# Python code here

IV. Bài toán minh họa

Ô tô điện: Bài toán yêu cầu tìm phạm vi di chuyển tối thiểu mà một chiếc xe điện cần có để di chuyển giữa các thành phố mà không hết điện. Giải pháp có thể sử dụng thuật toán Kruskal để tìm MST.

Động viên đàn bò: Tìm tổng thời gian tối thiểu để thăm tất cả các đàn bò trong một ngày, sử dụng MST đã tính đến thời gian trò chuyện với bò.

Bài viết này mong rằng sẽ giúp bạn nắm bắt được các khái niệm cũng như các thuật toán cần thiết cho bài toán cây khung nhỏ nhất một cách dễ dàng và hiệu quả.
source: viblo