không d a trên t t ng c a các thu t toán tìm ki m theo chi u r ng ho c chi u sâu.ự ư ưở ủ ậ ế ề ộ ặ ề
Trong các thu t toán này, t i t ng b c c a quá trình xây d ng T luôn là m t cây, chậ ạ ừ ướ ủ ự ộ ỉ
có đi u ki n v s đ nh c a T ph i đ n b c cu i cùng m i th a mãn. Còn trongề ệ ề ố ỉ ủ ả ế ướ ố ớ ỏ
thu t toán Kruskal, trong quá trình xây d ng T có th ch a là cây, nó ch th a mãn đi uậ ự ể ư ỉ ỏ ề
ki n không có chu trình.ệ
[s aử] Mô tả
Gi s G liên thông có n đ nh. G i T là cây bao trùm s xây d ng.ả ử ỉ ọ ẽ ự
1. Kh i t o: T lúc đ u là m t đ th r ng.ở ạ ầ ộ ồ ị ỗ
2. N u T đã g m đúng n-1 c nh c a G thì T là cây bao trùm c n tìm. K t thúc.ế ồ ạ ủ ầ ế
3. N u G còn ch a đ n-1 c nh, thì vì G liên thông, nên G có không ít h n n-1ế ư ủ ạ ơ
c nh, do đó còn các c nh c a G ch a thu c T. Trong các c nh c a G ch aạ ạ ủ ư ộ ạ ủ ư
thu c T có các c nh không t o ra chu trình v i các c nh đã có trong T, Ch nộ ạ ạ ớ ạ ọ
c nh v có tr ng s nh nh t trong các c nh y b sung (cùng v i các đ nh ch aạ ọ ố ỏ ấ ạ ấ ổ ớ ỉ ư
thu c T c a nó) vào T.ộ ủ
4. Quay l i 2.ạ
M t vài tác gi có cách trình bày khác c a gi i thu t Kruskal, tuy b n ch t quá trình làộ ả ủ ả ậ ả ấ
gi ng nhauố
1. Kh i t o: T lúc đ u g m t t c các đ nh c a G và ch a có c nh nào,nh vây Tở ạ ầ ồ ấ ả ỉ ủ ư ạ ư
lúc đ u là m t r ng n cây,m i cây g m đúng m t đ nh.ầ ộ ừ ỗ ồ ộ ỉ
2. N u T ch g m m t cây thì d ngế ỉ ồ ộ ừ
3. N u T g m nhi u h n m t cây, ch n c nh nh nh t c a G có hai đ u mútế ồ ề ơ ộ ọ ạ ỏ ấ ủ ầ
thu c hai cây khác nhau b sung vào T, khi đó hai cây đ c h p thành m t cây.ộ ổ ượ ợ ộ
4. Quay l i 2.ạ
[s aử] Gi mãả
[s aử] Phân tích
•Khi l p trình cài đ t gi i thu t Kruskal có hai đi m m u ch t c n chú ý:ậ ặ ả ậ ể ấ ố ầ
1. Trong m i l n l p ta ch n c nh có tr ng s nh nh t đ a vào T.ỗ ầ ặ ọ ạ ọ ố ỏ ấ ư
2. C nh đ c ch n đ a vào T ph i không t o thành chu trình v i các c nh đã cóạ ượ ọ ư ả ạ ớ ạ
trong T.
•V n đ th nh t đ c gi i quy t g n gi ng nh trong gi i thu t ấ ề ứ ấ ượ ả ế ầ ố ư ả ậ Prim là t oạ
m t hàng đ i có u tiên trên danh sách các c nh. Tuy nhiên có th ngay t đ uộ ợ ư ạ ể ừ ầ
s p x p các c nh theo th t tăng d n c a tr ng s .ắ ế ạ ứ ự ầ ủ ọ ố
Đ gi i quy t v n đ th hai, ta quay l i chú ý r ng, khác v i gi i thu t ể ả ế ầ ề ứ ạ ằ ớ ả ậ Prim, t i m iạ ỗ
b c c a gi i thu t ướ ủ ả ậ Kruskal, t p các đ nh và các c nh đã đ c đ a vào T ch a là câyậ ỉ ạ ượ ư ư
mà ch th a mã tính không chu trình. Nh v y t i m i b c T là m t r ng, T =ỉ ỏ ư ậ ạ ỗ ướ ộ ừ
.
•Bây gi xét m t c nh ờ ộ ạ e = (u,v) c a G ch a n m trong T có 3 kh năng x y ra:ủ ư ằ ả ả
1. C ảu,v ch a thu c T. Khi đó n u b sung ư ộ ế ổ e vào T thì không có chu trình, nh ngư
chính c nh ạe t o thành m t cây con m i.ạ ộ ớ
2. M t đ nh ch ng h n ộ ỉ ẳ ạ u thu c T, còn đ nh kia ộ ỉ v không thu c T. Vi c b sungộ ệ ổ
c nh ạe và đ nh ỉv vào T (vào cây con ch a đ nh ứ ỉ u) không t o ra chu trình.ạ
3. C ảu,v đ u n m trong T. Khi đó ề ằ
1. N u ếu,v n m trong cùng m t cây con ằ ộ Tk ta không th b sung canh ể ổ e vào
T.
2. N u ếu,v n m trong hai cây con khác nhau thì có th b sung c nh e vàoằ ể ổ ạ
T (hai đ nh u, v đã n m trong T không c n b sung, sau khi b sung haiỉ ằ ầ ổ ổ
cây con s h p l i thành m t cây.ẽ ợ ạ ộ
[s aử] T ch c d li uổ ứ ữ ệ
•Gi s G=(V,E)là đ th vô h ng n đ nh, cho b ng danh sách k Ajd(u),ả ử ồ ị ướ ỉ ằ ề
. Các đ nh c a G đ c đánh s t 1 đ n n, nghiã là V=V[1..n];Ta cũngỉ ủ ượ ố ừ ế
kí hi u Index(u) là ch s c a đ nh u trong m ng V.ệ ỉ ố ủ ỉ ả
Hàm tr ng s W(u,v) xác đ nh trên các c nh ọ ố ị ạ . V i m i c nh e=(u,v) kýớ ỗ ạ
hi u e.x u, e.y=v là hai đ nh liên thu c v i c nh e.ệ ỉ ộ ớ ạ
•Các bi n sau đ c đ a vào ế ượ ư
oHàng đ i Q c a các c nh x p theo th t tr ng s t nh đ n l n.ợ ủ ạ ế ứ ự ọ ố ừ ỏ ế ớ
oV i m i cây con, hàm PARENTS(u) xác đ nh trên V, bi u di n ch sớ ỗ ị ể ễ ỉ ố
c a đ nh cha c a đ nh u trong m t cây. Riêng đ nh g c u c a m i câyủ ỉ ủ ỉ ộ ỉ ố ủ ỗ
hàm PARENTS(u)l u tr s đ nh trong cây v i d u âm.ư ữ ố ỉ ớ ấ
[s aử] Mã
Procedure Kruskal (G)
T = V;
Q =Sort(E)
/* T o n cây, m i cây g m m t đ nh*/ạ ỗ ồ ộ ỉ
For each u of X do Parent(u):=-1;
m = |E|
For j:=1 to m do {
u:=NodeStart(Q(j)); V:=NodeEnd(Q(j))
If Find_tree(u)<>Find_tree(V) then
T:=T U Q[j];
Union(u,v;)
Ghi chú:
•Th t c Find_set(u) tìm đ nh g c c a cây ch a đ nh u. (xem ủ ụ ỉ ố ủ ứ ỉ cây bi u di n t pể ễ ậ
h pợ).
•Th t c Union(u,v),ghép cây ch a v vào cây ch a u (xem ủ ụ ứ ứ cây bi u di n t pể ễ ậ
h pợ).
L y t “ấ ừ http://vi.wikipedia.org/wiki/C%C3%A2y_bao_tr%C3%B9m_nh%E1%BB
%8F_nh%E1%BA%A5t”
Th lo iể ạ : Cây (c u trúc)ấ | Bài toán th i gian đa th cờ ứ | Gi i thu t lý thuy t đ thả ậ ế ồ ị
-------------------------------------------------------------------------------
#include <iostream.h>
char Dinhdau[] ={‘a’,’a’,’a’,’b’,’b’,’c’, ’c’,’d’};
char Dinhcuoi[] ={‘b’,’c’,’d’,’c’,’e’,’d’, ’f’,’g’};
int Trongso[] ={10, 1, 10,5,10,4,2,10};
int n = sizeof(Trongso)/sizeof(int);
int CanhCay = 7;
int Cay[100] ;// canh thu may
char Dinh[] = {‘a’,’b’,’c’,….};
int TPLT[] = {1,2,3,4,5,6,7};
int SapXep(){
for (int i = 0; i<n-1; i++){
int min = i;
for (int j = i+1; j<n; j++){
if (Trongso[min]>Trongso[j]) min = j;
}
if (min !=i){
int tg = Trongso[i]; Trongso[i] = Trongso[min]; Trongso[min]=tg;
char ch = Dinhdau[i]; Dinhdau[i]= Dinhdau[min]; Dinhdau[min] = ch;
ch = Dinhcuoi[i]; Dinhcuoi [i]= Dinhcuoi [min]; Dinhcuoi [min] = ch;
}
}
//--------------------------------------------------
void HopTPLT(int TP1, int TP2){
for (int i = 0; i<n; i++)
if (TPLT[i]= =TP1) TPLT[i]= TP2);
}
//-------------------------------------------------------------
int F_TPLT(char ch){
for (int i = 0; i<n; i++)
if(Dinh[i]==ch) return TPLT[i];
}
//---------------------------------------------------------------
int main(){
int Canh = 0;
SapXep();
int i = 0;
while (Canh <CanhCay){
if (F_TPLT(Dinhdau[i]) != F_TPLT(Dinhcuoi[i])){
Cay[Canh] = min;
Canh +=1;
HopTPLT(Dinhdau[i], Dinhcuoi[i]);
}
}
//-----------------------------------------------------------------------
Đ TÀI TÌM CÂY TR NG L NG NH NH T B NG GI I THU TỀ Ọ ƯỢ Ỏ Ấ Ằ Ả Ậ
KRUSCAL
MSĐT : NL1TH-025
Đ C T Đ TÀIẶ Ả Ề
V n d ng các lý thuy t c b n v đ th đ cài đ t ch ng trình cho phép bi u di nậ ụ ế ơ ả ề ồ ị ể ặ ươ ể ễ
đ th , ki m tra tính liên thông và tìm cây có tr ng l ng nh nh t b ng gi i thu tồ ị ể ọ ượ ỏ ấ ằ ả ậ
Kruscal.
YÊU C U C A Đ TÀIẦ Ủ Ề
Yêu c u c b n c n đ t đ c :ầ ơ ả ầ ạ ượ
Lý thuy t:ế
- Các thao tác c b n v đ h a.ơ ả ề ồ ọ
- Các khái ni m v đ th có h ng và đ th vô h ngệ ề ồ ị ướ ồ ị ướ
-Các cách bi u di n đ th , các ph ng pháp tìm ki m trên đ th (tìm theo chi u r ngể ễ ồ ị ươ ế ồ ị ề ộ
và chi u sâu) và tính liên thông.ề
- Gi i thu t ki m tra tính liên thông và gi i thu t Kruscal tìm cây có tr ng l ng nhả ậ ể ả ậ ọ ượ ỏ
nh t.ấ
-Nh ng c u trúc d li u c n thi t đ cài đ t ch ng trình.ữ ấ ữ ệ ầ ế ể ặ ươ
Ch ng trình: ươ
Ph i có nh ng ch c năng c b n sau:ả ữ ứ ơ ả
- C p nh t d li u v đ th .ậ ậ ữ ệ ề ồ ị
- Bi u di n đ th trên màn hình.ể ễ ồ ị
- Ki m tra tính liên thông.ể
- Cho phép tìm cây có tr ng l ng nh nh t.ọ ượ ỏ ấ
MÔI TR NG CÀI Đ T :ƯỜ Ặ
Ngôn ng l p trình s d ng : Pascal, C, C ữ ậ ử ụ ++
TÀI LI U THAM KH O :Ệ Ả
1. Bài gi ng: Lý Thuy t Đ th - Phan T n Tàiả ế ồ ị ấ
2. Lý Thuy t Đ Th - PTs. Nguy n Cam & PTs. Chu Đ c Khánh.ế ồ ị ễ ứ
3. Tóan r i r c – Nguy n Đ c Nghĩa & Nguy n Tô Thànhờ ạ ễ ứ ễ
4. “Tóan r i r c ng d ng trong tin h c” d ch t quy n Discrete Methamatíc and Itsờ ạ ứ ụ ọ ị ừ ể
Application – Mc Graw Hill.
5. Data Structures and Algorithms - A. Aho, J. Ullman
6. Ch ng trình = C u trúc d li u + Gi i thu t – Wirthươ ấ ữ ệ ả ậ
----------------------------------------------------------------
#include <iostream.h>
char Dinhdau[] ={'a','a' ,'a','b','b','c','c','d','e','e'};
char Dinhcuoi[] ={'b','e','f','c','e','d','e','e','f','g'};
int Trongso[] ={3,5,7,10,12,12,13,16,16,16};
int n = sizeof(Trongso)/sizeof(int);
int CanhCay = 9;
int Cay[100] ;
char Dinh[] = {'a','b','c','d','e','f'}; // sao lai char dinh la sao a
int TPLT[] = {1,2,3,4,5,6,7,8,9,10}; // cai TPLT nay la cai gi a
int SapXep()
{
for ( int i = 0; i<n-1; i++)
{
int min = i;
for (int j = i+1; j<n; j++)