Bài toán tìm cây khung tối thiểu (hay cây khung nhỏ nhất - Minimmum Spanning Tree - MST) của một đồ thị vô hướng là một bài toán rất nổi tiếng và có ứng dụng rất lớn, bài toán được phát biểu một cách cụ thể theo lý thuyết đồ thị như sau:
Cho đồ thị vô hướng có trọng số G=(V,E) được cho trước dữ liệu (bằng một trong các cách: Ma trận kề, Danh sách cạnh, Danh sách liên kết...). Tìm cây khung nhỏ nhất của G hay tìm một tập cạnh ECK Ì E có n-1 cạnh, n đỉnh, không có một chu trình nào và có tổng trọng số của các cạnh là nhỏ nhất.
Hiện nay, đã có rất nhiều thuật toán giải quyết bài toán MST trong các trường hợp cụ thể để giải quyết các bài toán thực tế. Các công trình nghiên cứu về đồ thị nói chung và Cây khung nói riêng vẫn tiếp tục được phát triển, nhằm mở rộng thêm phạm vi ứng dụng của đồ thị, các công bố mới nhất vào cuối năm 2003 của một số giáo sư người Israel.
1. Vấn đề biểu diễn đồ thị:
Đồ thị G như vậy có thể được biểu diễn theo nhiều cách. Tuy nhiên có hai cách thông dụng nhất, đơn giản cho việc lập trình, và càng đơn giản cho bài toán chúng ta đang xét đó là Ma trận kề và Danh sách cạnh.
a) Ma trận kề (Adjacency Matrix):
Giả sử G có n đỉnh, khi đó ma trận kề A có kích thước (n*n), nếu A[i,j]=0 nghĩa là đỉnh i và đỉnh j không có cạnh nối, nếu A[i,j]<>0 nghĩa là giữa đỉnh i và j có đường đi trực tiếp với trọng số chính là A[i,j].
Như vậy G vô hướng thì A[i,j]=A[j,i] với m-i i, j. Do đó ma trận A có thể được rút gọn một nửa để trở thành 'Tam giác kề' khi lưu trữ, nhưng khi cấp phát tĩnh bộ nhớ trong chương trình ta vẫn phải dùng ma trận A (n*n).
Ma trận kề là cấu trúc dữ liệu truy xuất nhanh nhất và sử dụng đơn giản nhất trong các bài toán đồ thị, trừ một số trường hợp cá biệt nó kém CTDL khác. Chẳng hạn với giải thuật tìm chu trình Euler, CTDL Danh sách kề liên kết mới là hiệu quả nhất về m-i mặt. Tuy nhiên ma trận kề lưu trữ rất tốn bộ nhớ, giới hạn của vùng nhớ cơ sở là 64K, như vậy ma trận kề chỉ được tối đa 256*256 phần tử kiểu byte, chưa tính các biến khác phải dùng.
b) Danh sách cạnh (Edges List):
Giả sử G có m cạnh, khi đó danh sách cạnh L có m phần tử, mỗi phần tử có 3 trường thể hiện đỉnh đầu, đỉnh cuối (của cạnh) và trọng số giữa chúng.
Danh sách cạnh như vậy có thể biểu diễn bằng một mảng một chiều m phần tử record 3 trường, hoặc 3 mảng một chiều rời nhau. Đây cũng là CTDL đơn giản, dễ sử dụng. Danh sách cạnh có những hạn chế như việc xác định 2 đỉnh có kề nhau hay không, loại bỏ cạnh, nhưng nó tốn ít bộ nhớ và trong một số trường hợp cụ thể nó tỏ ra rất ưu việt, như trong giải thuật Kruskal chẳng hạn.
Nhận xét:
Mỗi CTDL có những ưu điểm, nhược điểm khác nhau trong từng tình huống, từng giải thuật. Nhưng nhìn chung từ cách biểu diễn này hoàn toàn có thể biểu diễn sanh cách kia. Vậy chúng ta chọn CTDL nào cho bài toán này?
Cây khung thực chất là một đồ thị con G' của G với cùng tập đỉnh nhưng số cạnh ít hơn (hoặc bằng nếu G đã là một cây khung) sao cho G' thoả mãn là: Liên thông, Không có chu trình và có n-1 cạnh. Ta biểu diễn G' bằng danh sách cạnh là thích hợp nhất. Còn G để đơn giản và nhanh chóng chúng ta dùng ma trận kề.
2. Thuật toán Kruskal:
- Tư tưởng: Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất? tạm gọi là tập K, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau: Ưu tiên các cạnh có trọng số nhỏ hơn, kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó. Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n-1 cạnh sẽ là cây khung nhỏ nhất.
- Khi lập trình để có được sự ưu tiên, cách tốt nhất là sắp xếp trước các cạnh theo trọng số tăng dần. Điều này cũng gợi ý cho chúng ta thấy nên sử dụng danh sách cạnh trong giải thuật Kruskal, tuy nhiên để thống nhất đầu vào với giải thuật Prim trong chương trình, chúng ta sẽ sử dụng ma trận kề sau đó chuyển thành danh sách cạnh.
- Để kiểm tra xem cạnh đang xét có tạo chu trình không với tập cạnh đã kết nạp, chúng ta sử dụng một phương pháp đặc biệt mỗi khi kết nạp đó là: cho một đỉnh trở thành 'dad' của đỉnh kia. Với 2 đỉnh x, y bất kỳ, nếu 'dad cao nhất' của chúng bằng nhau thì cạnh nối x, y sẽ tạo nên chu trình (chu trình này đi qua 'dad' chung đó.
3. Thuật toán Prim:
- Do thuật toán Kruskal làm việc trên các cạnh nên sẽ kém hiệu quả nếu có quá nhiều cạnh? như các đồ thị dày (số cạnh m ≈ n(n-1)/2).
- Đối nghịch với Kruskal, thuật toán Prim làm việc trên các đỉnh, sẽ hiệu quả hơn với các đồ thị dày. Có thế thấy đa số các đồ thị trong thực tế có số đỉnh không lớn còn số cạnh rất lớn nên Prim tỏ ra hiệu quả hơn và?đắt giá? hơn Kruskal, mặc dù cài đặt có phức tạp hơn. Ngoại lệ, trong các trường hợp số cạnh rất ít còn số đỉnh rất nhiều thì Prim kém hiệu quả hơn Kruskal.
- Tư tưởng: Prim đề xuất cách xây dựng đồng thời tập đỉnh đã kết nạp (VH) và tập cạnh đã kết nạp T cho cây khung nhỏ nhất theo nguyên tắc như sau: Lần lượt kết nạp một đỉnh u thuộc VVH vào VH sao cho tồn tại v thuộc VH mà trọng số (u,v) là nhỏ nhất trong m-i cặp đỉnh nối VH và VVH
Cho đồ thị vô hướng có trọng số G=(V,E) được cho trước dữ liệu (bằng một trong các cách: Ma trận kề, Danh sách cạnh, Danh sách liên kết...). Tìm cây khung nhỏ nhất của G hay tìm một tập cạnh ECK Ì E có n-1 cạnh, n đỉnh, không có một chu trình nào và có tổng trọng số của các cạnh là nhỏ nhất.
Hiện nay, đã có rất nhiều thuật toán giải quyết bài toán MST trong các trường hợp cụ thể để giải quyết các bài toán thực tế. Các công trình nghiên cứu về đồ thị nói chung và Cây khung nói riêng vẫn tiếp tục được phát triển, nhằm mở rộng thêm phạm vi ứng dụng của đồ thị, các công bố mới nhất vào cuối năm 2003 của một số giáo sư người Israel.
1. Vấn đề biểu diễn đồ thị:
Đồ thị G như vậy có thể được biểu diễn theo nhiều cách. Tuy nhiên có hai cách thông dụng nhất, đơn giản cho việc lập trình, và càng đơn giản cho bài toán chúng ta đang xét đó là Ma trận kề và Danh sách cạnh.
a) Ma trận kề (Adjacency Matrix):
Giả sử G có n đỉnh, khi đó ma trận kề A có kích thước (n*n), nếu A[i,j]=0 nghĩa là đỉnh i và đỉnh j không có cạnh nối, nếu A[i,j]<>0 nghĩa là giữa đỉnh i và j có đường đi trực tiếp với trọng số chính là A[i,j].
Như vậy G vô hướng thì A[i,j]=A[j,i] với m-i i, j. Do đó ma trận A có thể được rút gọn một nửa để trở thành 'Tam giác kề' khi lưu trữ, nhưng khi cấp phát tĩnh bộ nhớ trong chương trình ta vẫn phải dùng ma trận A (n*n).
Ma trận kề là cấu trúc dữ liệu truy xuất nhanh nhất và sử dụng đơn giản nhất trong các bài toán đồ thị, trừ một số trường hợp cá biệt nó kém CTDL khác. Chẳng hạn với giải thuật tìm chu trình Euler, CTDL Danh sách kề liên kết mới là hiệu quả nhất về m-i mặt. Tuy nhiên ma trận kề lưu trữ rất tốn bộ nhớ, giới hạn của vùng nhớ cơ sở là 64K, như vậy ma trận kề chỉ được tối đa 256*256 phần tử kiểu byte, chưa tính các biến khác phải dùng.
b) Danh sách cạnh (Edges List):
Giả sử G có m cạnh, khi đó danh sách cạnh L có m phần tử, mỗi phần tử có 3 trường thể hiện đỉnh đầu, đỉnh cuối (của cạnh) và trọng số giữa chúng.
Danh sách cạnh như vậy có thể biểu diễn bằng một mảng một chiều m phần tử record 3 trường, hoặc 3 mảng một chiều rời nhau. Đây cũng là CTDL đơn giản, dễ sử dụng. Danh sách cạnh có những hạn chế như việc xác định 2 đỉnh có kề nhau hay không, loại bỏ cạnh, nhưng nó tốn ít bộ nhớ và trong một số trường hợp cụ thể nó tỏ ra rất ưu việt, như trong giải thuật Kruskal chẳng hạn.
Nhận xét:
Mỗi CTDL có những ưu điểm, nhược điểm khác nhau trong từng tình huống, từng giải thuật. Nhưng nhìn chung từ cách biểu diễn này hoàn toàn có thể biểu diễn sanh cách kia. Vậy chúng ta chọn CTDL nào cho bài toán này?
Cây khung thực chất là một đồ thị con G' của G với cùng tập đỉnh nhưng số cạnh ít hơn (hoặc bằng nếu G đã là một cây khung) sao cho G' thoả mãn là: Liên thông, Không có chu trình và có n-1 cạnh. Ta biểu diễn G' bằng danh sách cạnh là thích hợp nhất. Còn G để đơn giản và nhanh chóng chúng ta dùng ma trận kề.
2. Thuật toán Kruskal:
- Tư tưởng: Để xây dựng tập n-1 cạnh của cây khung nhỏ nhất? tạm gọi là tập K, Kruskal đề nghị cách kết nạp lần lượt các cạnh vào tập đó theo nguyên tắc như sau: Ưu tiên các cạnh có trọng số nhỏ hơn, kết nạp cạnh khi nó không tạo chu trình với tập cạnh đã kết nạp trước đó. Đó là một nguyên tắc chính xác và đúng đắn, đảm bảo tập K nếu thu đủ n-1 cạnh sẽ là cây khung nhỏ nhất.
- Khi lập trình để có được sự ưu tiên, cách tốt nhất là sắp xếp trước các cạnh theo trọng số tăng dần. Điều này cũng gợi ý cho chúng ta thấy nên sử dụng danh sách cạnh trong giải thuật Kruskal, tuy nhiên để thống nhất đầu vào với giải thuật Prim trong chương trình, chúng ta sẽ sử dụng ma trận kề sau đó chuyển thành danh sách cạnh.
- Để kiểm tra xem cạnh đang xét có tạo chu trình không với tập cạnh đã kết nạp, chúng ta sử dụng một phương pháp đặc biệt mỗi khi kết nạp đó là: cho một đỉnh trở thành 'dad' của đỉnh kia. Với 2 đỉnh x, y bất kỳ, nếu 'dad cao nhất' của chúng bằng nhau thì cạnh nối x, y sẽ tạo nên chu trình (chu trình này đi qua 'dad' chung đó.
3. Thuật toán Prim:
- Do thuật toán Kruskal làm việc trên các cạnh nên sẽ kém hiệu quả nếu có quá nhiều cạnh? như các đồ thị dày (số cạnh m ≈ n(n-1)/2).
- Đối nghịch với Kruskal, thuật toán Prim làm việc trên các đỉnh, sẽ hiệu quả hơn với các đồ thị dày. Có thế thấy đa số các đồ thị trong thực tế có số đỉnh không lớn còn số cạnh rất lớn nên Prim tỏ ra hiệu quả hơn và?đắt giá? hơn Kruskal, mặc dù cài đặt có phức tạp hơn. Ngoại lệ, trong các trường hợp số cạnh rất ít còn số đỉnh rất nhiều thì Prim kém hiệu quả hơn Kruskal.
- Tư tưởng: Prim đề xuất cách xây dựng đồng thời tập đỉnh đã kết nạp (VH) và tập cạnh đã kết nạp T cho cây khung nhỏ nhất theo nguyên tắc như sau: Lần lượt kết nạp một đỉnh u thuộc VVH vào VH sao cho tồn tại v thuộc VH mà trọng số (u,v) là nhỏ nhất trong m-i cặp đỉnh nối VH và VVH
