View Single Post
Old 01-01-1970, 07:00 AM   #10
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Post

CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ
4.Thuật toán Kruskal:

Xây dựng tập cạnh T của cây khung nhỏ nhất H=(V,T). Sắp xêp các cạnh của đồ thị G theo thứ tự không giảm của độ dài.
Bắt đầu T = Ø
Ở mỗi bước duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn để tìm ra cạnh mà việc bổ sung vào tập T không tạo thành chu trình trong tập này.
Thuật toán sẽ kết thúc khi ta thu được tập T gồm có n-1 cạnh.
Code:
 PROCEDURE KRUSKAL;
  BEGIN
   Sắp xếp các cạnh theo chiều không giảm;
    T = Ø;
  WHILE ( |T| < n-1 ) AND ( E <> Ø) DO
      BEGIN
           Chọn e in E là cạnh có độ dài nhỏ nhất.
             E:= E - {e};
             IF (T + {e}) không chứa chu trình THEN
             T:=T+{e}
            END;
      END;
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog

thay đổi nội dung bởi: myhanh, 24-08-2012 lúc 10:18 PM.
myhanh is offline   Trả Lời Với Trích Dẫn
Đã có 5 thành viên gửi lời cám ơn đến myhanh vì bạn đã đăng bài:
AldenSi (03-10-2018), Galenfar (29-09-2018), HatlodPi (14-01-2017), kenzaki (31-10-2008), TemmyVino (25-03-2017)