Thuật toán tìm cây khung nhỏ nhất theo Prim và Kruskul

Tìm cây khung nhỏ nhất của đồ thị sau theo thuật toán Kruskal và Prim.









Dùng thuật toán Kruskal:
Bước 1 : Sắp xếp các cạnh của đồ thị theo thứ tự trọng số tăng dần và khởi tạo cây T : = rỗng:
-Bắt đầu từ đồ thị rỗng T có 8 đỉnh.Sắp xếp theo trọng số tăng dần
1=>3=>3=>4=>5=>7=>9=>10=>11=>14=>15=>20=>42
{(d,e);(b,f);(c,d);(a,c);(d,g);(g,h);(h,f);(a,e);(e,f);(b,e);(c,g);(d,h);(a,b)}

Bước 2: Duyệt theo cạnh e thuộc danh sách đã sắp xếp.Nếu T + {e} không chứa chu trình thì ghép e vào cây : T= T+{e}
Thêm vào đồ thị T cạnh (d,e),do 1<8-1(định lý cây T liên thông có n-1 cạnh,n là đỉnh) =>Thêm vào đồ thị T cạnh (c,d),do 2<8-1
=>Thêm vào đồ thì T cạnh (b,f),do 3<8-1
=>Thêm vào đồ thị T cạnh (a,c),do 4<8-1
=>Thêm vào đồ thị T cạnh (d,g),do 5<8-1
=>Thêm vào đồ thị T cạnh (g,h),do 6<8-1
=>Thêm vào đồ thị T cạnh (h,f),do 7=8-1 nên cây đủ cạnh.Kết thúc.Ta thu được cây sau: {(d,e);(c,d);(b,f);(a,c);(d,g);(g,h);(h,f)}
Cây tạo thành theo thuật toán Kruskal như sau:










Dùng thuật toán Prim:
Bước 1 : tùy chọn 1 đỉnh x0 = X và khởi tạo V :={x0
}(V là tập đỉnh); T = rỗng.(T là tập cạnh khởi tạo chưa có cạnh)
Bước 2: Trong số những cạnh nối đỉnh đã chọn với đỉnh y ta chọn cạnh e có trọng số nhỏ nhất.Nếu không có cạnh e thì dừng
Bước 3 : Gán V:= V hợp với {y} và T:= T hợp với {e}
Bước 4: nếu T đủ n-1 cạnh thì dừng,ngược lại làm tiếp bước 2
Thuật toán Prim cho bài này như sau:
-Chọn đỉnh a
-(a,c) có trọng số 3 nhỏ nhát nên ta chọn cạnh này.
-Trong số các cạnh nối với 2 đỉnh a và c cạnh (c,d) có trọng số nhỏ nhất nên ta chọn (c,d)
-Trong các cạnh nối với 3 đỉnh a,c và d cạnh (d,e ) có trọng số nhỏ nhất nên chọn (d,e)
-Tương tự ta có các cạnh tiếp đến hết : (d,g);(g,h);(h,f);(f,b)

copy hình không được bực thiệt:
Ai biết thì chỉ nhé;
Hình tạm là thế này các bạn tự vẽ nhá:
Đềbài:(a,b)=42;(a,e)=10;(a,c)=4;(b,e)=14;(b,f)=3;(c,d)=3;(c,g)=15);(d,e)=1;(d,h)=20;(d,g)=5;
(e,f)=11;(f,h)=9;(g,h)=7;

THANKS! MÌNH ĐÃ HIỂU!