Tìm kiếm
Latest topics
THUẬT TOÁN KRUSKAL
bkiz :: Giáo Trình :: Toán Rời Rạc
Trang 1 trong tổng số 1 trang
THUẬT TOÁN KRUSKAL
Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau:
a. Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh;
b. Xuất phát từ tập cạnh T=φ, ở mỗi bước, ta sẽ lần lượt duyệt trong danh sách các cạnh đã
được sắp xếp, từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn để tìm ra cạnh mà khi
bổ sung nó vào T không tạo thành chu trình trong tập các cạnh đã được bổ sung vào T
trước đó;
c. Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.
Thuật toán được mô tả thông qua thủ tục Kruskal như sau:
void Kruskal(void){
T = φ;
While ( | T | < (n-1) and (E≠ φ ) ){
Chọn cạnh e ∈E là cạnh có độ dài nhỏ nhất;
E:= E\ {e};
if (T ∪ {e}: không tạo nên chu trình )
T = T ∪ {e};
}
if ( | T | <n-1)
Đồ thị không liên thông;
}
Chương trình tìm cây khung nhỏ nhất theo thuật toán Kruskal được thể hiện như sau:
a. Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh;
b. Xuất phát từ tập cạnh T=φ, ở mỗi bước, ta sẽ lần lượt duyệt trong danh sách các cạnh đã
được sắp xếp, từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn để tìm ra cạnh mà khi
bổ sung nó vào T không tạo thành chu trình trong tập các cạnh đã được bổ sung vào T
trước đó;
c. Thuật toán sẽ kết thúc khi ta thu được tập T gồm n-1 cạnh.
Thuật toán được mô tả thông qua thủ tục Kruskal như sau:
void Kruskal(void){
T = φ;
While ( | T | < (n-1) and (E≠ φ ) ){
Chọn cạnh e ∈E là cạnh có độ dài nhỏ nhất;
E:= E\ {e};
if (T ∪ {e}: không tạo nên chu trình )
T = T ∪ {e};
}
if ( | T | <n-1)
Đồ thị không liên thông;
}
Chương trình tìm cây khung nhỏ nhất theo thuật toán Kruskal được thể hiện như sau:
Similar topics
» Thuật toán Dijkstra
» Thuật toán Floy
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS)
» Thuật toán DDA (Digital Differential Analizer)
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search)
» Thuật toán Floy
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS)
» Thuật toán DDA (Digital Differential Analizer)
» THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (Breadth First Search)
bkiz :: Giáo Trình :: Toán Rời Rạc
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|
Mon Jun 24, 2013 11:27 pm by hangme
» host facebook
Mon Apr 02, 2012 2:26 pm by Admin
» Cyberlink PowerDirector 9 key full
Thu Mar 29, 2012 5:00 pm by Admin
» PowerDirector 10 Ultra
Fri Mar 23, 2012 6:15 pm by Admin
» Mảng - Nhập mảng số nguyên, tính tổng phần tử dương, tìm số hoàn hảo, tìm max, min, sắp xếp từ lớn đến nhỏ, từ nhỏ đến lớn
Sun Mar 18, 2012 9:17 pm by Admin
» HTML+CSS Form đăng nhập
Tue Sep 13, 2011 10:38 pm by Admin
» HTML+javascript : Lịch Dương
Thu Sep 08, 2011 5:15 pm by Admin
» HTML+javascript : Đòng hồ điện tử
Thu Sep 08, 2011 5:06 pm by Admin
» HTML: Form Đăng nhập
Thu Sep 08, 2011 4:42 pm by Admin