PHƯƠNG PHÁP THAM LAM
Bài 5.4. Cây bao trùm ngắn nhất
Cho một đồ thị liên thông G vô hướng bao gồm n đỉnh, mã số từ 1 đến n, và m cạnh nối hai đỉnh với nhau. Mỗi cạnh có chiều dài cho trước. Tính liên thông của đồ thị cho biết với hai đỉnh cho trước tuỳ ý ta luôn tìm được các cạnh gối đầu nhau để đi từ đỉnh này đến đỉnh kia. Hãy chỉ ra một phần P của đồ thị thoả các tính chất sau:
(i) P chứa tất cả các đỉnh của G;
(ii) P chứa một số ít nhất các cạnh của G;
(iii) P là đồ thị liên thông;
(iv) Tổng chiều dài các cạnh của P là ngắn nhất.
Đồ thị P thoả ba tính chất (i), (ii) và (iii) được gọi là cây bao trùm của đồ thị G.
Nếu P thoả thêm tính chất (iv) thì P được gọi là cây bao trùm ngắn nhất của G. Một số tài liệu dùng thuật ngữ cây khung thay cho cây bao trùm và cây khung cực tiểu thay cho cây bao trùm ngắn nhất.
Bài toán trên có nhiều ứng dụng thực tiễn. Một trong số ứng dụng đó được mô tả thông qua thí dụ sau:
Có n máy tính được nối với nhau thành mạng bằng cáp quang là một loại dây truyền tin đắt tiền. Trong mạng này, hai máy tính bất kì đều có thể liên lạc được với nhau trực tiếp hoặc thông qua một vài máy trung gian. Ta gọi tính chất này là tính liên thông của mạng máy tính. Hãy bỏ bớt một số dây nối để n máy tính trên vẫn liên thông được với nhau. Mạng tối thiểu thu được chính là một cây bao trùm ngắn nhất của mạng ban đầu.
Dữ liệu vào: tệp văn bản tên DOTHI.INP.
- Dòng đầu tiên ghi hai số tự nhiên n và m cách nhau qua dấu cách, biểu thị số đỉnh (n) và số cạnh (m) của đồ thị.
- Mỗi dòng thứ i = 1, 2,..., m trong số m dòng tiếp theo ghi ba giá trị x y và d cách nhau qua dấu cách với ý nghĩa cạnh (x, y) của đồ thị có chiều dài d.
Dữ liệu ra: tệp văn bản tên DOTHI.OUT bao gồm:
- Danh sách các cạnh được chọn.
- Dòng cuối cùng ghi tổng chiều dài tìm được.
Thuật toán
Ta dùng thuật giải Kruskal với kĩ thuật như sau. Duyệt các cạnh từ chiều dài nhỏ đến lớn. Cạnh được chọn sẽ là cạnh không tạo thành chu trình khi ghép nó vào đồ thị kết quả.
DOTHI.INP 8 17 1 2 8 1 3 4 1 4 6 1 5 1 1 6 2 2 3 2 2 4 7 3 4 9 3 7 4 3 8 3 4 5 5 4 6 5 4 8 1 5 6 6 6 7 8 6 8 7 7 8 1
Ý nghĩa: Đồ thị có 8 đỉnh và 17 cạnh.
Cạnh (1, 2) dài 8, cạnh (1, 3) dài 4, cạnh (1, 4) dài 6, ..., cạnh (7, 8) dài 1 đơn vị.
DOTHI.OU T 1 5 4 8 7 8 2 3 1 6 3 8 1 3 14
Ý nghĩa: Cây bao trùm ngắn nhất của đồ thị đã cho gồm 8 đỉnh và 7 cạnh là (chiều dài mỗi cạnh được ghi sau dấu hai chấm):
cạnh 1. (1, 5): 1 cạnh 2. (4, 8): 1 cạnh 3. (7, 8): 1 cạnh 4. (2, 3): 2 cạnh 5. (1, 6): 2 cạnh 6. (3, 8): 3 cạnh 7. (1, 3): 4
Tổng chiều dài 7 cạnh đã chọn là: 14.
Lưu ý rằng đồ thị kết quả thu được ở các bước trung gian có thể không liên thông mà bao gồm nhiều mảnh liên thông (cây con). Loại đồ thị này được gọi là rừng. Kết quả cuối cùng sẽ là cây vì nó liên thông và được tạo thành từ n - 1 cạnh. Ta vận dụng tổ chức find-union cho các tập đỉnh rời nhau để quản lí các tập đỉnh được chọn nhằm phát hiện chu trình. Cạnh (x, y) khi được ghép vào đồ thị trung gian sẽ tạo thành chu trình khi và chỉ khi các đỉnh x và y cùng nằm trong một cây của đồ thị (rừng) trung gian đó.
Như vậy mỗi cây con của đồ thị trung gian được quản lí như một tập con của tập các đỉnh 1..n của đồ thị ban đầu. Tập con này có phần tử đại diện chính là gốc của cây tương ứng. Phần tử này được chọn theo mã số nhỏ nhất. Các đỉnh còn lại của cây con đều trỏ đến gốc đó.
Dễ thấy cây bao trùm luôn luôn có n đỉnh và n - 1 cạnh.
(* Pascal *)
(*--- DOTHI.PAS Cay bao trum ngan nhat (thuat giai Kruskal)
---*) program DoThi;
uses crt;
const
MN = 100; bl = #32; {dau cach}
fn = 'DoThi.inp'; gn = 'DoThi.out';
nl = #13#10; {xuong dong}
type { Mo ta mot canh cua do thi } CANH = record
x,y: integer; {canh (x,y) } len: integer; { do dai canh } end;
var
a: array[0..MN] of CANH; { Mang cac canh }
d: array[1..MN] of integer;{dung cho find-union } n: integer; {n: so dinh }
m: integer; {so canh } f,g: text;
procedure Doc; (* Doc du lieu *) var i: integer;
begin
assign(f,fn); reset(f);
read(f,n,m);
for i := 1 to m do
read(f,a[i].x,a[i].y,a[i].len);
close(f);
end;
(* Sap canh tang theo len *) procedure qsort(d,c: integer);
var
i,j,m: integer;
t: CANH;
begin
i := d;
j := c;
m := a[(i+j) div 2].len; {diem giua}
while (i<=j) do
begin
while a[i].len < m do i := i+1;
while a[j].len > m do j := j-1;
if i<=j then begin
t := a[i];
a[i] := a[j];
a[j] := t;
i := i+1; j := j-1;
end;
end;
if d < j then qsort(d,j);
if i < c then qsort(i,c);
end;
{Tim dai dien cua tap chua x } function Find(x: integer): integer;
begin
while x <> d[x] do x := d[x];
Find := x;
end;
{---
Hop nhat 2 tap dinh: tap chua dinh x va tap chua dinh y.
Union = false: Neu canh (x,y) tao thanh chu trinh.
Union = true: Neu (x,y) khong tao thanh chu trinh.
---}
function Union(x,y: integer): Boolean;
begin
Union := false;
x := Find(x);
y := Find(y);
if x = y then exit;
if x < y then d[y] := x else d[x] := y;
Union := true;
end;
procedure CBTNN;(* Cay bao trum ngan nhat *) var
i, t: integer;
k: integer;
begin
assign(g,gn); rewrite(g);
for i := 1 to n do d[i] := i; {Khoi tri } k := 0;
t := 0; {tong chieu dai cac canh}
for i := 1 to m do
{duyet cac canh theo chieu dai tang dan } if Union(a[i].x,a[i].y) then
begin
writeln(g,a[i].x,bl,a[i].y);
t := t + a[i].len;
inc(k);
if k=n-1 then break;{chon duoc n-1 canh la du }
end;
writeln(g,t);
close(g);
end;
BEGIN
Doc; qsort(1,m);
CBTNN; readln;
END.
// C#
using System;
using System.IO;
namespace SangTao1 {
/*--- * Cay khung (cay bao trum) * ngan nhat
* ---*/
class CayKhung {
const string fn = "DoThi.inp";
const string gn = "DoThi.out";
// do thi co n dinh // m canh (u,v)
// u la dinh dau, v - dinh cuoi // Len - chieu dai canh
static int[] d ; // to chuc Find-Union static int n = 0; // so dinh cua do thi static int m = 0; // so canh cua do thi static Canh[] cc; // Tap cac canh
static int [] t; // canh duoc chon static int k; // so canh duoc chon static int sum = 0;
static void Main() {
Doc(); QSort(0, m-1);
Ghi(); Test();
Console.WriteLine("Fini");
Console.ReadLine();
} // Main static void Xep() {
d = new int[n+1];
t = new int [n];
k = 0; sum = 0;
// Khoi tri cho Find-Union
for (int i = 1; i <= n; ++i) d[i] = i;
for (int i = 0; i < m; ++i) if (Union(cc[i].U,cc[i].V)) { t[k++] = i; sum += cc[i].Len; } }
static void Ghi() {
StreamWriter g = File.CreateText(gn);
for (int i = 0; i < k; ++i) cc[t[i]].FWrite(g);
g.WriteLine(sum); g.Close();
}
static int Find(int x) {
while (d[x] != x) x = d[x];
return x;
}
// Hop nhat 2 tap dinh
// tap chua dinh u va tap chua dinh v static bool Union(int u, int v)
{
u = Find(u); v = Find(v);
if (u == v) return false;
if (u < v) d[v] = u; else d[u] = v;
return true;
}
// Sap cac canh tang dan theo Len static void QSort(int d, int c) {
int i = d, j = c;
int m = cc[(d + c) / 2].Len;
Canh t = new Canh(0,0,0);
while (i <= j) {
while (cc[i].Len < m) ++i;
while (m < cc[j].Len) --j;
if (i <= j) {
t = cc[i]; cc[i] = cc[j];
cc[j] = t;
++i; --j;
} }
if (d < j) QSort(d, j);
if (i < c) QSort(i, c);
}
// Doc lai file gn de kiem tra ket qua static void Test() tự viết
static void Doc() {
int[] b =
Array.ConvertAll((File.ReadAllText(fn)).Split(
new char[] {'\n',' ','\t','\0','\r'}, StringSplitOptions.RemoveEmptyEntries), new Converter<string, int>(int.Parse));
n = b[0];// so dinh m = b[1]; // so canh // Tach du lieu cc = new Canh[m];
for (int k = 2, i = 0; i < m; ++i, k += 3) cc[i] = new Canh(b[k], b[k + 1], b[k + 2]);
} // Doc
public struct Canh // Mo ta canh {
public int U; // dinh dau
public int V; // dinh cuoi u < v public int Len;
public Canh(int d1, int d2, int d) {
if (d1 < d2) { U = d1; V = d2; } else { U = d2; V = d1; }
Len = d;
}
public void Print() {
Console.WriteLine(U + " " + V + " " + Len);
}
public void Print2()
{ Console.WriteLine(U + " " + V); } public void FWrite(StreamWriter f) { f.WriteLine(U + " " + V); }
}
} // CayKhung } // SangTao1