Cây khung bài toán Pascal
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (91.08 KB, 6 trang )
Cây khung
Bùi Thị Thuỳ Dung
Khái niệm về cây khung được CayLey đưa ra năm 1857. Cây là đồ thị vô hướng,liên
thông, không có chu trình.Trong tin học, cây được dùng để xây dựng các thuật toán, tổ
chức các thư mục, các thuật toán tìm kiếm, lưu trữ và nén dữ liệu,..Có rất nhiều dạng bài
tập về cây như: sửa chữa đường, định chiều các đường đi trong thành phố, tìm cây khung
có nhiều lá nhất,...
Và một bài toán quan trọng trong cấu trúc dữ liệu cây chính là tìm Cây khung nhỏ nhất.
I. Phát biểu bài toán:
Có n máy tính được đánh số từ 1 đến n, chi phí nối máy i với máy j là c[i,j] (i,j = 1..n). Hãy
tìm cách nối mạng đảm bảo hai máy tính bất kì có thể truyền dữ liệu cho nhau và chi phí
nối mạng là nhỏ nhất.
Dữ liệu vào từ file văn bản mintree.inp:
- dòng 1: ghi số n là số máy tính
trong các dòng tiếp theo, mỗi dòng ghi 3 số i, j , c[i,j] cách nhau một dấu cách thể hiện nối
máy i và máy j mất chi phí c[i,j].
Xuất ra file mintree.out :
- Dòng 1: ghi tổng chi phí nối mạng
- N - 1 dòng tiếp theo mỗi dòng 2 số i,j thể hiện nối máy i với máy j.
II. Thuật giải:
Trên đây là mô hình thực tế của cây khung nhỏ nhất, chúng ta có thể giải quyết bài toán
bằng cách liệt kê tất cả các cây khung của đồ thị và chọn ra cây khung nhỏ nhất. Phương
pháp đó đòi hỏi thời gian cỡ n
n
- 2. Như vậy, ngay cả với đồ thị cỡ hàng chục cũng không
mấy khả thi, song hãy để ý đến tính chất 'nhỏ nhất' của cây khung cần tìm chúng ta sẽ tìm
ra những giải pháp khả quan hơn, đó chính là thuật toán KRUSKAL và PRIM.
1. Phương pháp Kruskal (1857):
Thuật toán bắt đầu với một rừng n cây: trong n - 1 bước, nó kết hợp hai cây với nhau (sử
dụng cạnh ngắn nhất có thể) cho đến khi còn lại một cây.
Như vậy có hai vấn đề quan trọng khi cài đặt:
- Thứ nhất: làm thế nào để có thể sử dụng cạnh ngắn nhất một cách nhanh nhất: ta có thể
sắp xếp danh sách cạnh theo thứ tự tăng dần của trọng số và duyệt từ đầu tới cuối danh
sách. Trong trường hợp tổng quát thì HeapSort tỏ ra hiệu quả hơn cả.
- Thứ hai: làm thế nào để kiểm tra xem cạnh (u,v) có thuộc hai cây khác nhau hay không?
Nếu ta cho mỗi đỉnh v trên cây một nhãn Lab[v] là số hiệu đỉnh cha của đỉnh v trong cây,
trong trường hợp v là gốc của một cây thì Lap[v] được gán một giá trị âm. Khi đó ta có thể
xác định được gốc cây chứa v bằng hàm sau:
function GetRoot(v : integer): integer;
begin
while lab[v] > 0 do v: = lab[v];
GetRoot: = v;
end;
{Vì mỗi cây chỉ có một gốc nên v và u ở khác cây
r1 = GetRoot(u) # GeetRoot(v) = r2 ;
Để hợp nhất hai cây gốc r1 và r2 ta chỉ cần đặt Lab[r2] : = r1;
Cụ thể, thuật toán có thể mô t như sau:
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
program KrusKal;
const
fi = 'mintree.inp';
fo = 'mintree.out';
max = 100;
maxe = max * (max - 1) div 2;
type
TEdge = record
u,v,c : integer;
mark : boolean;
end;
var
a : array [1..maxe] of Tedge;
lab : array [1..max] of integer;
{Lab[v] là đỉnh cha của v, nếu v là gốc thì lab[v] = - số con cây gốc v}
n,m : integer;
procedure readfile;
var
f : text;
i : integer;
begin
assign(f,fi); reset(f);
readln(f,n);
m := 0;
while not SeekEof(f) do
begin
inc(m);
with a[m] do readln(f,u,v,c);
end;
close(f);
end;
procedure init;
var
i : integer;
begin
for i := 1 to n do lab[i] := -1;{ban đầu, mỗi cây đều chỉ có một nút}
for i := 1 to n do a[i].mark := false;
end;
procedure adjust(r,last : integer);
var
key : TEdge;
i : integer;
begin
key := a[r];
i := 2 * r;
while i < a[i + 1].c) do inc(i);
if key.c > 0 then v := lab[v];
GetRoot := v;
end;
procedure union(r1,r2 : integer);{hợp nhất hai cây thành một cây}
var
x : integer;
begin
x := lab[r1] + lab[r2];{-x là số nút của cả hai cây}
if lab[r1] > lab[r2] then {cây gốc r1 ít hút hơn cây gốc r2, hợp nhất thành cây gốc r2}
begin
lab[r1] := r2;
lab[r2] := x;
end
else
begin
lab[r2] := r1;
lab[r1] := x;
end;
end;
procedure solve;
var
i : integer;
r1,r2 : integer;
count : integer;
tmp : TEdge;
begin
count := 0;
for i := m div 2 downto 1 do adjust(i,m);
for i := m - 1 downto 1 do
begin
tmp := a[1]; a[1] := a[i + 1]; a[i + 1] := tmp;
adjust(1,i);
r1 := GetRoot(a[i + 1].u); r2 := GetRoot(a[i+1].v);
if r1<> r2 then {cạnh a[i + 1] nối hai cây khác nhau}
begin
a[i +1].mark := true;
inc(count);
if count = n - 1 then exit;
union(r1,r2);
end;
end;
end;
procedure result;
var
f : text;
w : integer;
i : integer;
beginw := 0;
for i := 1 to m do
with a[i] do
if a[i].mark then w := w + c;
assign(f,fo); rewrite(f);
writeln(f,w);
for i := 1 to m do
with a[i] do
if a[i].mark then writeln(f,u,' ',v);
close(f);
end;
begin
readfile;
init;
solve;
result;
end.
Vì thuật toán Kruskal luôn lấy những cạnh nhỏ nhất có thể tại mỗi bước nên trong các
cây khung nhỏ nhất, cây Kruskal có trọng số cạnh lớn nhất là nhỏ nhất.
2. Phương pháp PRIM:
Thuật toán Kruskal hoạt động chậm khi đồ thị dày (có số cạnh lớn m > n(n -1)/ 2).
Trong trường hợp đó, người ta thường sử dụng phương pháp lân cận của Prim.
Thuật toán có thể phát biểu như sau:
Bắt đầu từ một đỉnh u bất kì của đồ thị, gọi v là đỉnh gần u nhất (nghĩa là trong số các cạnh
kề của u thì cạnh (u,v) có độ dài nhỏ nhất). Tiếp theo, trong số những cạnh kề với u hoặc v
ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba t, ta thu được cây gồm 3 đỉnh
2 cạnh. Quá trình này sẽ tiếp tục cho đến khi ta tìm được cây khung gồm n đỉnh và n - 1
cạnh sẽ chính là cây khung nhỏ nhất cần tìm.
Thuật toán được mô tả trong chương trình sau:
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
program Prim;
const
fi = 'mintree.inp';
fo = 'mintree.out';
max = 100;
type
Ta1 = array [1..max,1..max] of integer;
Ta2 = array [1..max] of integer;
Ta3 = array [1..max] of boolean;
var
c : Ta1;{c[u,v] là trọng số của cạnh (u,v) }
d : Ta2;{d[v] = khoảng cách nhỏ nhất từ v tới cây T đang xét}
free : Ta3;{free[v] = true nếu v chưa bị kết nạp vào cây T}
trace : Ta2;{ trace[v] = đỉnh cha tương ứng của v trong cây T}
n : integer;
procedur readfile;
var
f : text;
i,j : integer;
begin
for i := 1 to max do
for j := 1 to max do c[i,j] := maxint;
assign(f,fi); reset(f);
readln(f,n);
while not SeekEof(f) do
begin
readln(f,i,j,c[i,j]);
c[j,i] := c[i,j];
end;
close(f);
end;
procedure init;var
i : integer;
begin
for i := 1 to n do d[i] := maxint;
fillchar(free,sizeof(free),true);
fillchar(trace,sizeof(trace),0);
end;
procedure solve;
var
min : integer;
imin : integer;
i,j : integer;
k : integer;
begin
d[1] := 0;
for k := 1 to n do
begin
min := maxint;
for i := 1 to n do
if free[i] and (d[i] >c[imin,i]) then
begin
d[i] := c[imin,i];
trace[i] := imin;
end;
