tailieunhanh - Toán rời rạc part 8

Tham khảo tài liệu 'toán rời rạc part 8', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Phần 2. Lý thuyết đồ thị Chú ý rằng mỗi tập con trong phân hoạch có thể lưu trữ như ỉà một cây có gốc và khi đó mỗi gốc sẽ được sử dụng làm nhãn nhận biết tập con tương ứng. Chương trình trên Pascal thực hiện thuật toán Kruskal với những nhận xét vừa nêu có thể viết như sau Tìm cây khung nhỏ nhất theo thuật toán Kruskal của đồ thị cho bởi danh sách cạnh uses crt type arm array l 50 of integer arrm - array 1 .5000 of integer var n m MinL integer Dau Cuoi w arrm DauT CuoiT Father arm Connect boolean procedure Nhapdl var i integer fname string f text begin writei Cho Tên file dữ liệu readln fname assign f fname reset f readln f n m for i - 1 to m do readln f Dau iJ Cuoi i W i closc f end procedure Indulieu var i integer begin writelnf So đỉnh n . Số cạnh m writeln Đỉnh đầu Đỉnh cưôì Độ dài for i to m do writeln Dau i 4 Cuoi i 10 W i 12 end 208 Chương 5. Cây vá Cây khung của đồ thị procedure HeapfFirst Last integer var j k tl t2 t3 integer begin j first while j trunc last 2 do begin if 2 j last and W 2 j 1 W 2 j then k -2 j l else k 2 j if W k W j then begin tl Dau j t2 Cuoi j t3 W j Dau j Dau k Cuoi j Cuoi k W j W k Dau k tl Cuoi k t2 W k t3 j k end else j Last end end function Find i integer integer var Tro integer begin Tro i while Father Tro 0 do Tro Father Tro Find Tro end procedure Union i j integer var x integer begin X Father i Father j if Father i Fatherfj then begin Father i j Father j x end else 28- TRR 209 Phẩn 2. Lý íhuyết đổ íhị begin Fatherlj i Fatherfi x end end procedure Kruskal var i Last u V rl r2 Ncanh Ndinh integer begin Khởi tạo mảng Father đánh dấu cây con và khởi tạo Heap for i l to n do Father i -1 for i trunc m 2 down to 1 do Heap i m last m Ncanh 0 Ndinh 0 MinL 0 Connect true while Ndinh n-1 and Ncanh m do begin Ncanh Ncanh 1 u Dau l V Cuoi l Kiểm tra u và V có thuộc cùng một cây con rl Find u r2 Find v if rl r2 then begin Kết nạp cạnh u v vào cây khung Ndinh Ndinh l Union rl r2 DauT Ndinh u CuoiT Ndinh v MinL MínL W 1 end Tổ chức lại Heap .