BÀI TẬP
CHƯƠNG 4. LÝ THUYẾT ĐỒ THỊ
Bài 1: Liệt kê kết quả từng bước thực hiện duyệt đồ thị theo 2 dạng: + Duyệt sâu (DFS) + Duyệt rộng (BFS)? a b c e d f g m h k
Bài 2: Hãy tìm cây khung nhỏ nhất bằng thuật toán Prim và thuật toán Kruskal
của đồ thị được cho bởi ma trận trọng số sau. A B C D E F H I
A   14 17 19 23 22 32 18    B 14  33 15 34 19 20 12    C 17 33   13 29 21 20 19  D 19 15 13  22 30 31 11    .
E  23 34 29 22  34 23 21  F 22 19 21 30 34   17 16  
H 32 20 20 31 23 17  14   
I 18 12 19 11 21 16 14  
Yêu cầu: Nêu ý tưởng thuật toán và viết các kết quả trung gian trong từng bước lặp
(lập bảng), kết quả cuối cùng cần đưa ra tập cạnh và độ dài của cây khung nhỏ nhất.
Bài 3: Tìm cây khung của đồ thị sau theo 2 thuật toán duyệt sâu (DFS), duyệt rộng (BFS)? -----------------------