Bài toán tìm cây khung nhỏ nhất (hay cây khung tối thiểu - Minimum Spanning Tree - MST) của đồ thị vô hướng liên thông có trọng số là một bài toán tối ưu nổi tiếng và có ứng dụng rất lớn. Cho G=(V,E) là đồ thị vô hướng liên thông có trọng số, với một cây khung T của G, ta gọi trọng số của cây T là tổng trọng số các cạnh. Bài toán đặt ra là trong số các cây khung của G, chỉ ra cây khung T có trọng số nhỏ nhất, T gọi là cây khung nhỏ nhất của đồ thị G (hình 2). Đã có nhiều thuật toán được tìm ra để giải quyết vấn đề này: Kruskal, Prim, Karger-Klein-Tarjan…, trong đó, một thuật toán rất hiệu quả và được tìm ra sớm nhất là thuật toán Sollin.

Thuật toán này lần đầu tiên được công bố bởi Otakar Boruvka năm 1926 như một phương pháp hiệu quả để thiết kế các mạng điện. Sau đó nó được các nhà khoa học khác tìm ra: Choquet năm 1938, Florek, Lukasiewicz, Perkal, Steinhaus, and Zubrzycki năm 1951, và một lần nữa nó được công bố bởi Sollin năm 1960. Vì Sollin là một nhà khoa học máy tính nên trong các tài liệu trình bày về thuật toán này, đặc biệt là các tài liệu về tính toán song song, nó thường được gọi với cái tên Sollin's algorithm. Thuật toán được trình bày dưới dạng giả mã như sau:

Quá trình dựng cây khung nhỏ nhất theo thuật toán sollin đuợc thực hiện bằng cách, coi mỗi đỉnh của đồ thị là nút gốc của một cây, khi đó ta được một rừng và khởi tạo cây khung T ban đầu không có cạnh nào. Tiếp theo, với mỗi một cây ta lựa chọn cạnh nối một nút trong cây với một nút của cây khác (để đảm bảo không tạo ra chu trình trong T) có trọng số nhỏ nhất (hình 3b) thêm vào cây khung T, cập nhật hai cây có cạnh nối với nhau tạo thành một cây. Lặp lại quá trình này cho đến khi T có N-1 cạnh và cây khung được dựng hoàn chỉnh (hình 3c).

Ta sẽ cài đặt thuật toán Sollin bằng ngôn ngữ C++. Chương trình sau được viết và biên dịch trên MS Visual Studio 2005, tuy nhiên nếu máy tính của bạn đang dùng Linux, bạn có thể biên dịch nó với Dev-C++. Sau khi kởi động Ms Visual Studio bạn chọn kiểu Project C++ và Templates là Win32 Console Application, đặt tên cho project là Sollin, soạn thảo với nội dung như sau:

Khác với thuật toán Kruskal và Prim, Sollin lựa chọn nhiều cạnh trong mỗi một bước, và thuật toán có thể dễ dàng được song song hoá. Độ phức tạp về thời gian trung bình của thuật toán là O(E*log V) với E là số cạnh, V là số đỉnh của đồ thị. Mặc dù Sollin giản dị và thực sự hiệu quả, nhưng nó lại ít khi được đề cập đến trong các sách về cấu trúc dữ liệu và thuật toán. Hi vọng với trình bày sơ lược trên đây về thuật toán “cũ” này sẽ đem đến cho các bạn những cảm nhận thú vị “mới” về bài toán cây khung nhỏ nhất.

( Bùi Văn Tân - Tanbv_it@yahoo.com )

School@net (Theo THNT)