Giáo trình thực hành lý thuyết đồ thị va thuật giải

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP CỬU LONG KHOA CÔNG NGHỆ THÔNG TIN W€X GIÁO TRÌNH THỰC HÀNH LÝ THUYẾT ĐỒ THỊ VÀ THUẬT GIẢI Biên Soạn: ĐÀO ANH PHA Vĩnh Long, 05/2006 Giáo Trình Thực Hành Lý Thuyết Đồ Thị MỤC LỤC MỘT SỐ BÀI TỐN...................................................................................................2 BÀI TỐN 1.................................................................................................................2 BÀI TỐN 2.................................................................................................................3 BÀI TỐN 3.................................................................................................................4 BÀI TỐN 4.................................................................................................................5 BÀI TỐN 6.................................................................................................................7 BÀI TỐN 7.................................................................................................................8 BÀI TỐN 8.................................................................................................................9 BÀI TỐN 9...............................................................................................................10 BÀI TỐN 10.............................................................................................................11 HƯỚNG DẪN CÀI ĐẶT BÀI TỐN......................................................................12 BÀI TỐN 1...............................................................................................................12 BÀI TỐN 2...............................................................................................................17 BÀI TỐN 3...............................................................................................................20 BÀI TỐN 4...............................................................................................................22 BÀI TỐN 5...............................................................................................................25 BÀI TỐN 6...............................................................................................................32 BÀI TỐN 7...............................................................................................................35 BÀI TỐN 8...............................................................................................................38 BÀI TỐN 9...............................................................................................................43 BÀI TỐN 10.............................................................................................................48 Biên Soạn: Đào Anh Pha Trang 1 Giáo Trình Thực Hành Lý Thuyết Đồ Thị MỘT SỐ BÀI TỐN BÀI TỐN 1 Viết chương trình tìm bậc cao nhất của đỉnh trong đồ thị với đồ thị vơ hướng A[i,j] với A[i,j]=1 nếu cĩ đường đi từ i đến j và ngược lại A[i,j] = 0 nếu khơng cĩ đường đi từ i đến j. Dữ liệu vào: cho trong file Bai1.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100). - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: thơng báo kết quả ra màn hình số bậc cao nhất của đỉnh trong đồ thị đã cho. Ví dụ: Bai1.inp Kết quả: 6 Bac cao nhat: 4 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 Bai1.inp Kết quả: 5 Bac cao nhat: 4 0 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 0 Yêu cầu xử lý: a) Tìm đỉnh cĩ bậc cao nhất. b) Tìm bậc nhỏ nhẩt của đỉnh. c) Tìm đỉnh cĩ bậc nhỏ nhất. d) Tính tổng bậc của đồ thị. e) Đếm số đỉnh bậc chẵn và bậc lẻ. Ví dụ: Kết quả: a) Đỉnh 2,5. b) Bậc 2. c) Đỉnh 1,3,4. d) Tổng bậc của đồ thị 14. e) Số đỉnh bậc chẵn 5, số đỉnh bậc lẻ 0. Biên Soạn: Đào Anh Pha Trang 2 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 2 Viết chương trình kiểm tra tính liên thơng của một đồ thị vơ hướng A[i,j] với A[i,j]=1 nếu cĩ đường đi từ i đến j và ngược lại A[i,j] = 0 nếu khơng cĩ đường đi từ i đến j. Dữ liệu vào: cho trong file Bai2.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100). - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: thơng báo kết quả ra màn hình ”DO THI LIEN THONG” hay “ DO THI KHONG LIEN THONG”. Ví dụ: Bai2.inp Kết quả: 5 DO THI LIEN THONG 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 Bai2.inp Kết quả: 8 DO THI LIEN THONG 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 Bai2.inp Kết quả: 6 DO THI KHONG LIEN THONG 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Biên Soạn: Đào Anh Pha Trang 3 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 3 Viết chương trình đếm số thành phần liên thơng của đồ thị vơ hướng Anxn với: - A[i,j] = 1 nếu cĩ đường đi từ i đến j. - A[i,j] = 0 nếu khơng cĩ đường đi từ i đến j. - A[i,j] = A[j,i]. Dữ liệu vào: cho trong file Bai2.inp nội dung dữ liệu giống dữ liệu Bài Tốn 2. Dữ liệu ra: hiển thị số thành phần liên thơng của đồ thị ra màn hình. Ví dụ: Bai3.inp Kết quả: 6 2 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Bai3.inp Kết quả: 5 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 Bai3.inp Kết quả: 8 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 Biên Soạn: Đào Anh Pha Trang 4 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 4 Cĩ n thành phố biết rằng đường đi giữa hai các thành phố (nếu cĩ) là đường đi hai chiều. Sơ đồ mạng lưới giao thơng của n thành phố cho bởi ma trận Anxn trong đĩ: a. A[i,j] = 1 nếu cĩ đường đi từ thành phố i đến thành phố j. b. A[i,j] = 0 nếu khơng cĩ đường đi từ thành phố i đến thành phố j. c. A[i,j] = A[j,i]. Hãy xác định mọi đường từ thành phố D đến thành phố C (nếu cĩ). Dữ liệu vào: cho trong file Bai4.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng thứ hai lưu đỉnh D và đỉnh C. - Dịng i+2 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: Xuất ra màn hình mọi đường đi từ đỉnh D đến C hay thơng báo khơng tồn tại đường đi từ D đến C. Ví dụ: Bai4.inp Kết quả: 5 1->2->3->4->5 1 5 1->2->4->5 0 1 0 0 1 1->5 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 Bai3.inp Kết quả: 5 1->2->3->4->5 1 5 1->2->5 0 1 0 1 1 1->4->3->2->5 1 0 1 0 1 1->4->5 0 1 0 1 0 1->5 1 0 1 0 1 1 1 0 1 0 Bai4.inp Kết quả: 6 KHONG CO DUONG DI TU 1 DEN 4 1 4 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Biên Soạn: Đào Anh Pha Trang 5 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 5 Một lưới giao thơng hai chiều giữa n địa điểm được cho bởi ma trận A[i,j] trong đĩ A[i,j]=1 nếu cĩ đường đi từ i đến j, cịn A[i,j] = 0 trong trường hợp ngược lại. Một người đưa thơ cần đi qua tất cả các con đường này để phát thơ, mỗi đường chỉ qua một lần. Hãy xác định một lộ trình của người đưa thơ này (cĩ thể tồn tại nhiều lộ trình khác nhau) hay thơng báo khơng tồn tại đường như vậy. Dữ liệu vào: cho trong file Bai5.inp. - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: In ra màn hình đường đi của người đưa thơ (nếu cĩ). Ví dụ: Bai5.inp Kết quả: 5 1->2->3->4->2->5->4 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 Bai5.inp Kết quả: 5 KHONG TON TAI DUONG DI 0 1 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 Bai5.inp Kết quả: 5 2->1->5->4->2->3->4 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 Biên Soạn: Đào Anh Pha Trang 6 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 6 Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n, mỗi thành phố người khách chỉ muốn đi qua chúng một lần. Mạng lưới giao thơng giữa n thành phố là hai chiều và được cho bởi ma trận A[i,j] trong đĩ A[i,j] =1 nếu cĩ đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại. Hãy viết chương trình thiết lập cho người khách một lộ trình (cĩ thể tồn tại nhiều lộ trình) hay thơng báo khơng tồn tại lộ trình theo yêu cầu của khách. Dữ liệu vào: cho trong file Bai6.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng 2 ghi đỉnh mà người khách du lịch xuất phát. - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: In ra màn hình đường đi của người khách (nếu cĩ). Ví dụ: Bai6.inp Kết quả: 5 1->2->3->4->5 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 Bai6.inp Kết quả: 6 KHONG TON TAI DUONG DI 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 Bai6.inp Kết quả: 6 KHONG TON TAI DUONG DI 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Biên Soạn: Đào Anh Pha Trang 7 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 7 Cĩ n thành phố biết rằng đường đi giữa các thành phố là đường đi hai chiều. Sơ đồ mạng lưới giao thơng của n thành phố cho bởi ma trận A[i,j] trong đĩ: - A[i,j] là độ dài đường đi từ thành phố i đến thành phố j. - A[i,j] = 0 nếu khơng cĩ đường đi từ thành phố i đến thành phố j. - A[i,j] = A[j,i] - A[i,j] nguyên, khơng âm. Hãy xác định đường đi ngắn nhất từ thành phố D đến thành phố C. Dữ liệu vào: đồ thị đã liên thơng và cho trong file Bai7.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng thứ hai lưu đỉnh D và đỉnh C. - Dịng i+2 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: xuất ra màn hình đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được. Ví dụ: Bai7.inp Kết quả: 6 DUONG DI NGAN NHAT LA: 5 1 6 1->2->4->6 0 1 2 0 0 0 1 0 2 2 3 0 2 2 0 5 4 0 0 2 5 0 3 2 0 3 4 3 0 4 0 0 0 2 4 0 Bai7.inp Kết quả: 6 DUONG DI NGAN NHAT LA: 8 1 6 1->2->4->6 0 1 4 0 0 0 1 0 2 6 5 0 4 2 0 7 3 0 0 6 7 0 0 1 0 5 3 0 0 3 0 0 0 1 3 0 Biên Soạn: Đào Anh Pha Trang 8 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 8 Một cơng ty cần thay tồn bộ hệ thống dây điện cho n phịng làm việc. Cho biết sơ đồ điện hiện cĩ của n căn phịng này được biều diễn bằng ma trận A[i,j] trong đĩ: - A[i,j]=A[j,i] chính là chiều dài dây điện nối liền giữa hai phịng i và j. - A[i,j] = A[j,i] = 0 nếu i khơng nối liền với j. Hãy lập trình tính độ dài cuả dây dẫn cần sử dụng sao cho cả n phịng điều cĩ điện và số lượng này là ít nhất. Dữ liệu vào: cho trong file Bai8.inp (đồ thị cho đã liên thơng). - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: lưu trong file Bai8.out với nội dung sau: - Dịng đầu lưu độ dài dây dẫn nhỏ nhất - Các dịng cịn lại lưu đường đi cần nối điện giữa đỉnh i nối với đỉnh j cĩ trọng số A[i,j] (i -> j = A[i][j]). Ví dụ: Bai8.inp Bai8.out 5 0 3 3 2 2 3 0 2 3 2 3 2 0 1 4 2 3 1 0 4 2 2 4 4 0 7 1 -> 4 = 2 4 -> 3 = 1 1 -> 5 = 2 3 -> 2 = 2 Bai8.inp Bai8.out 8 0 2 3 4 0 0 0 0 2 0 3 0 4 0 0 0 3 3 0 7 6 5 2 0 4 0 7 0 0 0 3 0 0 4 6 0 0 4 0 8 0 0 5 0 4 0 1 6 0 0 2 3 0 1 0 5 0 0 0 0 8 6 5 0 20 1 -> 2 = 2 1 -> 3 = 3 3 -> 7 = 2 7 -> 6 = 1 7 -> 4 = 3 2 -> 5 = 4 7 -> 8 = 5 Biên Soạn: Đào Anh Pha Trang 9 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 9 Cĩ n thành phố được đánh số từ 1 đến n. Mạng lưới giao thơng giữa các thành phố là đường hai chiều. Trên đường đi từ thành phố i đến thành phố j, người ta khơng được mang quá A[i,j] đơn vị hàng. Nếu khơng cĩ đường đi từ thành phố i đến thành phố j thì xem như A[i,j] = 0. Cần vận chuyển hàng từ thành phố D đến thành phố C. Hãy thiết lập kế hoạch vận chuyển sao cho khối lượng hàng vận chuyển là nhiều nhất. Dữ liệu vào: đồ thị đã liên thơng và cho trong file Bai9.inp với nội dung - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng thứ hai lưu đỉnh D và đỉnh C. - Dịng i+2 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: xuất ra màn hình kế hoạch vận chuyển từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được. Ví dụ: Bai9.inp Kết quả: 6 KHOI LUONG VAN CHUYEN NHIEU NHAT LA: 2 1 6 1->3->4->6 0 1 2 0 0 0 1 0 2 2 3 0 2 2 0 5 4 0 0 2 5 0 3 2 0 3 4 3 0 4 0 0 0 2 4 0 Bai9.inp Kết quả: 6 KHOI LUONG VAN CHUYEN NHIEU NHAT LA: 3 1 6 1->3->4->2->5->6 0 1 4 0 0 0 1 0 2 6 5 0 4 2 0 7 3 0 0 6 7 0 0 1 0 5 3 0 0 3 0 0 0 1 3 0 Biên Soạn: Đào Anh Pha Trang 10 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 10 Cĩ n thành phố biết rằng đường đi giữa các thành phố là đường đi hai chiều. Sơ đồ mạng lưới giao thơng của n thành phố cho bởi ma trận A[i,j] trong đĩ: - A[i,j] là độ dài đường đi từ thành phố i đến thành phố j. - A[i,j] = 0 nếu khơng cĩ đường đi từ thành phố i đến thành phố j. - A[i,j] = A[j,i]. - A[i,j] nguyên, khơng âm. Hãy xác định đường đi dài nhất từ thành phố D đến thành phố C với điều kiện thành phố đã qua khơng được đi lại. Dữ liệu vào: đồ thị đã liên thơng và cho trong file Bai10.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng thứ hai lưu đỉnh D và đỉnh C. - Dịng i+2 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: xuất ra màn hình đường đi dài nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được. Ví dụ: Bai10.inp Kết quả: 6 DUONG DI DAI NHAT LA: 16 1 6 1->2->4->3->5->6 0 1 2 0 0 0 1 0 2 2 3 0 2 2 0 5 4 0 0 2 5 0 3 2 0 3 4 3 0 4 0 0 0 2 4 0 Bai10.inp Kết quả: 6 DUONG DI DAI NHAT LA: 25 1 6 1->3->4->2->5->6 0 1 4 0 0 0 1 0 2 6 5 0 4 2 0 7 3 0 0 6 7 0 0 1 0 5 3 0 0 3 0 0 0 1 3 0 Biên Soạn: Đào Anh Pha Trang 11 Giáo Trình Thực Hành Lý Thuyết Đồ Thị HƯỚNG DẪN CÀI ĐẶT BÀI TỐN BÀI TỐN 1 Viết chương trình tìm bậc cao nhất của đỉnh trong đồ thị với đồ thị vơ hướng A[i,j] với A[i,j]=1 nếu cĩ đường đi từ i đến j và ngược lại A[i,j] = 0 nếu khơng cĩ đường đi từ i đến j. Dữ liệu vào: cho trong file Bai1.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100). - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: thơng báo kết quả ra màn hình số bậc cao nhất của đỉnh trong đồ thị đã cho. Ví dụ: Bai1.inp Kết quả: 6 Bac cao nhat: 4 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 Bai1.inp Kết quả: 5 Bac cao nhat: 4 0 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 0 Yêu cầu xử lý: f) Tìm đỉnh cĩ bậc cao nhất. g) Tìm bậc nhỏ nhẩt của đỉnh. h) Tìm đỉnh cĩ bậc nhỏ nhất. i) Tính tổng bậc của đồ thị. j) Đếm số đỉnh bậc chẵn và bậc lẻ. Ví dụ: Kết quả: f) Đỉnh 2,5. g) Bậc 2. h) Đỉnh 1,3,4. i) Tổng bậc của đồ thị 14. Số đỉnh bậc chẵn 5, số đỉnh bậc lẻ 0. Biên Soạn: Đào Anh Pha Trang 12 Giáo Trình Thực Hành Lý Thuyết Đồ Thị HƯỚNG DẪN CÀI ĐẶT Tổng số phần tử khác khơng trên dịng i của ma trận liên kết của đồ thị chính là số bậc của đỉnh i (i=1..n). 9 Bậc lớn nhất của đỉnh: Tính bậc từng đỉnh của đồ thị, so sánh tìm ra bậc lớn nhất. 9 Đỉnh cĩ bậc lớn nhất: Tính bậc từng đỉnh của đồ thị, so sánh với bậc lớn nhất của đồ thị nếu bằng thì xuất đỉnh cĩ bậc lớn nhất ra màn hình. 9 Bậc nhỏ nhất của đỉnh: Tính bậc từng đỉnh của đồ thị, so sánh tìm ra bậc nhỏ nhất. 9 Đỉnh cĩ bậc nhỏ nhất: Tính bậc từng đỉnh của đồ thị, so sánh với bậc nhỏ nhất của đồ thị nếu bằng thì xuất đỉnh cĩ bậc nhỏ nhất ra màn hình. 9 Tìm đỉnh bậc lẻ và số đỉnh bậc lẻ: Tính bậc từng đỉnh của đồ thị, kiểm tra đỉnh tương ứng cĩ phải là bậc lẻ hay khơng nếu phải xuất ra màn hình và tăng số đỉnh bậc lẻ lên 1. 9 Tìm đỉnh bậc chẵn và số đỉnh bậc chẵn: tương tự như tìm số đỉnh bậc lẻ. 9 Tổng bậc của đồ thị: Tổng tất cả các phần tử khác khơng của ma trận liên kết chính là tổng số bậc của đồ thị. CHƯƠNG TRÌNH MẪU #include #include #include #include #define TenFile "Bai1.inp" /*Dọc file dữ liệu bài tốn*/ void Doc_File(int **A,int &n) { FILE*f = fopen(TenFile,"rb"); fscanf(f,"%d",&n); *A = new int [n]; cout<<"Ma Tran Lien Ket Cua Do Thi"; for(int i =0;i<n;i++) { A[i] = new int [n]; cout<<endl; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<" "<<A[i][j]; } } fclose(f); } /*Bậc lớn nhất của đỉnh*/ int BacLonNhat(int**A,int n) { int max = 0,Bac; Biên Soạn: Đào Anh Pha Trang 13 Giáo Trình Thực Hành Lý Thuyết Đồ Thị for(int i = 0; i<n; i++) { Bac = 0; for(int j = 0; j<n; j++) if(A[i][j]>0) Bac++; if(Bac > max) max = Bac; } return max; } /*Bậc nhỏ nhất của đỉnh*/ int BacNhoNhat(int**A,int n){ int min = MAXINT,Bac; for(int i = 0; i<n; i++) { Bac = 0; for(int j = 0; j<n; j++) if(A[i][j]>0) Bac++; if(Bac < min) min = Bac; } return min; } /*Tổng bậc của đồ thị*/ int TongBac(int**A,int n){ int Tong = 0; for(int i = 0; i<n; i++) for(int j = 0; j<n; j++) if(A[i][j]>0) Tong++; return Tong; } /*Các đỉnh cĩ bậc nhỏ nhất*/ void DinhBacNhoNhat(int**A, int n){ int min = BacNhoNhat(A,n), Bac; for(int i = 0; i<n; i++) { Bac = 0; for(int j = 0; j<n; j++) if(A[i][j]>0) Bac++; if(Bac == min) cout<<" "<<i+1; Biên Soạn: Đào Anh Pha Trang 14 Giáo Trình Thực Hành Lý Thuyết Đồ Thị } } /*Các đỉnh cĩ bậc lớn nhất*/ void DinhBacLonNhat(int**A, int n){ int max = BacLonNhat(A,n), Bac; for(int i = 0; i<n; i++) { Bac = 0; for(int j = 0; j<n; j++) if(A[i][j]>0) Bac++; if(Bac == max) cout<<" "<<i+1; } } /*Các đỉnh bậc chẵn và số đỉnh bậc chẵn*/ void DinhBacChan(int**A, int n) { int Bac,Tong=0; for(int i = 0; i<n; i++) { Bac = 0; for(int j = 0; j<n; j++) if(A[i][j]>0) Bac++; if(Bac%2==0) { cout<<" "<<i+1; Tong++; } } cout<<"\n\t So Dinh Bac Chan: "<<Tong; } /*Các đỉnh bậc lẻ và số đỉnh bậc lẻ*/ void DinhBacLe(int**A, int n){ int Bac,Tong=0; for(int i = 0; i<n; i++) { Bac = 0; for(int j = 0; j<n; j++) if(A[i][j]>0) Bac++; if(Bac%2==1) { cout<<" "<<i+1; Tong++; } } Biên Soạn: Đào Anh Pha Trang 15 Giáo Trình Thực Hành Lý Thuyết Đồ Thị cout<<"\n\t So Dinh Bac Le: "<<Tong; } /*Chuong Trinh Chinh*/ void main() { clrscr(); int **A,n; Doc_File(A,n); cout<<"\n1. Bac Lon Nhat Cua Dinh: "<<BacLonNhat(A,n); cout<<"\n2. Dinh Co Bac Lon Nhat:"; DinhBacLonNhat(A,n); cout<<"\n3. Bac Nho Nhat Cua Dinh: "<<BacNhoNhat(A,n); cout<<"\n4. Dinh Co Bac Nho Nhat:"; DinhBacNhoNhat(A,n); cout<<"\n5. Dinh Co Bac Chan:"; DinhBacChan(A,n); cout<<"\n6. Dinh Co Bac Le:"; DinhBacLe(A,n); cout<<"\n7. Tong Bac Cua Do Thi: "<<TongBac(A,n); delete*A; getch(); } Biên Soạn: Đào Anh Pha Trang 16 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 2 Viết chương trình kiểm tra tính liên thơng của một đồ thị vơ hướng A[i,j] với A[i,j]=1 nếu cĩ đường đi từ i đến j và ngược lại A[i,j] = 0 nếu khơng cĩ đường đi từ i đến j. Dữ liệu vào: cho trong file Bai2.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100). - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: thơng báo kết quả ra màn hình ”DO THI LIEN THONG” hay “ DO THI KHONG LIEN THONG”. Ví dụ: Bai2.inp Kết quả: 5 DO THI LIEN THONG 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 Bai2.inp Kết quả: 8 DO THI LIEN THONG 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 Bai2.inp Kết quả: 6 DO THI KHONG LIEN THONG 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Biên Soạn: Đào Anh Pha Trang 17 Giáo Trình Thực Hành Lý Thuyết Đồ Thị HƯỚNG DẪN THUẬT TỐN Ý tưởng: Sử dụng thuật tốn loang . Bước 1: Xuất phát từ một đỉnh bất kỳ của đồ thị. Ta đánh dấu đỉnh xuất phát và chuyển sang bước 2. Bước 2: Từ một đỉnh i đã đánh dấu, ta đánh dấu đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang bước 3. Bước 3: Thực hiện bước 2 cho đến khi khơng cịn thực hiện được nữa chuyển sang bước 4. Bước 4: Kiểm tra nếu số đỉnh đánh dấu nhỏ hơn n (hay tồn tại ít nhất một đỉnh chưa được đánh dấu) đồ thị sẽ khơng liên thơng và ngược lại đồ thị liên thơng. HƯỚNG DẪN CÀI ĐẶT Tổ chức cấu trúc dữ liệu để lưu trữ sự đánh dấu các đỉnh của đồ thị. ¾ Ta tổ chức một mảng 1 chiều (char*DanhDau) để lưu trữ những đỉnh của đồ thị cĩ được đánh dấu hay khơng. Chỉ số của mảng chính là chỉ số đỉnh của đồ thị. ¾ DanhDau[i]=0 nếu đỉnh i chưa được đánh dấu và DanhDau[i]=1 nếu đỉnh i đã được đánh dấu. Ví dụ: DanhDau[5]=1, DanhDau[3]=0 cĩ nghĩa là đỉnh thứ 5 của đồ thị đã được dánh đấu và đỉnh thứ 3 của đồ thị chưa được dánh dấu. ¾ Trong thuật tốn, trước tiên ta khởi tạo tất cả các đỉnh của đồ thị là chưa được đánh dấu. Nghĩa là DanhDau[i]=0, i=0..n-1. o Dánh dấu đỉnh dầu tiên của đồ thị (DanhDau[0]=1). o Từ đỉnh i đã đánh dấu (DanhDau[i]=1), ta đánh dấu đỉnh j (DanhDau[j]=1) nếu A[i][j] = 1 và j chưa được đánh dấu (DanhDau[j]=0). Cứ tiếp tục như vậy cho đến khi khơng thực hiện được nữa. o Nếu đỉnh nào chưa đánh dấu (tồn tại DanhDau[k]=0, 0≤k<n) thì đồ thị khơng liên thơng và ngược lại. CHƯƠNG TRÌNH MẪU #include #include #include #define TenFile "Bai2.inp" /*Dọc file dữ liệu*/ void Doc_File(int **A,int &n){ FILE*f = fopen(TenFile,"rb"); fscanf(f,"%d",&n); *A = new int [n]; cout<<"Ma Tran Lien Ket Cua Do Thi"; for(int i =0;i<n;i++) { A[i] = new int [n]; cout<<endl; Biên Soạn: Đào Anh Pha Trang 18 Giáo Trình Thực Hành Lý Thuyết Đồ Thị for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<" "<<A[i][j]; } } fclose(f); } /*Kiểm tra liên thơng: Nếu liên thơng trả về giá trị 1, ngược lại trả về giá trị 0*/ char Lien_Thong(int **A,int n) { char*DanhDau = new char [n]; char ThanhCong; int Dem=0; for(int i = 0; i<n; i++) DanhDau[i] = 0; DanhDau[0] = 1; Dem++; do { ThanhCong =1; for(i = 0; i<n; i++) if(DanhDau[i]==1) { for(int j = 0; j<n; j++) if (DanhDau[j] == 0 && A[i][j] > 0) { DanhDau[j] = 1; ThanhCong =0; Dem++; if(Dem == n) return 1; } } }while (ThanhCong == 0); return 0; } /*Chương trình chính*/ void main() { clrscr(); int **A,n; Doc_File(A,n); if (Lien_Thong(A,n)==1) cout<<"\nDO THI LIEN THONG"; else cout<<"\nDO THI KHONG LIEN THONG"; delete *A; getch(); } Biên Soạn: Đào Anh Pha Trang 19 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 3 Viết chương trình đếm số thành phần liên thơng của đồ thị vơ hướng Anxn với: - A[i,j] = 1 nếu cĩ đường đi từ i đến j. - A[i,j] = 0 nếu khơng cĩ đường đi từ i đến j. - A[i,j] = A[j,i]. Dữ liệu vào: cho trong file Bai2.inp nội dung dữ liệu giống dữ liệu Bài Tập2. Dữ liệu ra: hiển thị số thành phần liên thơng của đồ thị ra màn hình. Ví dụ: Bai3.inp Kết quả: 6 2 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Bai3.inp Kết quả: 5 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 Bai3.inp Kết quả: 8 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 HƯỚNG DẪN THUẬT TỐN Ý tưởng: Sử dụng thuật tốn loang giống như bài tốn 1. Bước 0: Khởi tạo số thành phần liên thơng bằng 0. Bước 1: Xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thơng lên 1 và chuyển sang bước 2. Bước 2: Từ một đỉnh i đã đánh dấu, ta đánh dấu đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang bước 3. Biên Soạn: Đào Anh Pha Trang 20 Giáo Trình Thực Hành Lý Thuyết Đồ Thị Bước 3: Thực hiện bước 2 cho đến khi khơng cịn thực hiện được nữa chuyển sang bước 4. Bước 4: Nếu số số đỉnh đánh dấu bằng n (mọi đỉnh đều được đánh dấu) kết thúc thuật tốn, ngược lại quay về bước 1. Chú ý: Nếu số thành phần liên thơng bằng 1 đồ thị liên thơng. HƯỚNG DẪN CÀI ĐẶT Cài đặt tương tự như bài tốn 2. CHƯƠNG TRÌNH MẪU /*Hàm trả về số thành phần liên thơng của đồ thị vơ hướng */ int TPLien_Thong(int **A, int n) { char*DanhDau = new char [n]; char ThanhCong; int Dem=0, i,j, MLT=0; for( i = 0; i<n; i++) DanhDau[i] = 0; do { j = 0; while(DanhDau[j]==1) j++; DanhDau[j] = 1; Dem++; MLT++; do { ThanhCong =0; for(i = 0; i<n; i++) if(DanhDau[i]==1) for(j = 0; j<n; j++) if (DanhDau[j] == 0 && A[i][j] > 0) { DanhDau[j] = 1; ThanhCong =1; Dem++; if(Dem == n) return MLT; } }while (ThanhCong == 1); } while(Dem<n); return MLT; } Biên Soạn: Đào Anh Pha Trang 21 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 4 Cĩ n thành phố biết rằng đường đi giữa hai các thành phố (nếu cĩ) là đường đi hai chiều. Sơ đồ mạng lưới giao thơng của n thành phố cho bởi ma trận Anxn trong đĩ: d. A[i,j] = 1 nếu cĩ đường đi từ thành phố i đến thành phố j. e. A[i,j] = 0 nếu khơng cĩ đường đi từ thành phố i đến thành phố j. f. A[i,j] = A[j,i]. Hãy xác định mọi đường từ thành phố D đến thành phố C (nếu cĩ). Dữ liệu vào: đồ thị liên thơng và cho trong file Bai4.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng thứ hai lưu đỉnh D và đỉnh C - Dịng i+2 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: Xuất ra màn hình mọi đường đi từ đỉnh D đến C hay thơng báo khơng tồn tại đường đi từ D đến C. Ví dụ: Bai4.inp Kết quả: 5 1->2->3->4->5 1 5 1->2->4->5 0 1 0 0 1 1->5 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 Bai3.inp Kết quả: 5 1->2->3->4->5 1 5 1->2->5 0 1 0 1 1 1->4->3->2->5 1 0 1 0 1 1->4->5 0 1 0 1 0 1->5 1 0 1 0 1 1 1 0 1 0 Bai4.inp Kết quả: 6 KHONG CO DUONG DI TU 1 DEN 4 1 4 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Biên Soạn: Đào Anh Pha Trang 22 Giáo Trình Thực Hành Lý Thuyết Đồ Thị HƯỚNG DẪN THUẬT TỐN Sử dụng kỹ thuật tìm kiếm theo chiều sâu. HƯỚNG DẪN CÀI ĐẶT Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy. CHƯƠNG TRÌNH MẪU #include #include #include #define FileIn "Bai4.inp" int Dem = 0; //Dếm số đường đi int*L; //Lưu lại đường đã đi char*DanhDau; //Đánh dấu đỉnh đã đi int **A,n,D,C; /*Dọc file dữ liệu theo yêu cầu của chương trình*/ void Doc_File(){ FILE*f = fopen(FileIn,"rb"); fscanf(f,"%d%d%d",&n,&D,&C); cout<<"Ma Tran Lien Ket Tuong Ung.\n"; cout<<D<<" "<<C<<endl; *A = new int [n]; for(int i =0;i<n;i++) { A[i] = new int [n]; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" "; } cout<<endl; } fclose(f); D--; C--; } /*Khởi tạo các tham số ban đầu cho chương trình*/ void KhoiTao() { DanhDau = new char [n]; L = new int [n]; for (int i = 0; i<n; i++) { //Tất cả các đỉnh chưa được đánh dấu DanhDau[i] = 0; L[i] = 0; } Biên Soạn: Đào Anh Pha Trang 23 Giáo Trình Thực Hành Lý Thuyết Đồ Thị DanhDau[D] = 1; //Đánh dấu đỉnh đầu tiên L[0] = D; //Lưu lại đỉnh đầu tiên là đỉnh xuất phát } void InDuongDi(int SoCanh) { Dem++; cout<<endl<<D+1; for (int i = 1; i<SoCanh; i++) cout "<<L[i]+1; } /*Thủ tục đệ quy tìm kiếm đường đi*/ void TimKiem(int SoCanh) { if(L[SoCanh-1] == C) InDuongDi(SoCanh); else { for(int i = 0; i<n; i++) if( A[L[SoCanh-1]][i]>0 && DanhDau[i] == 0){ L[SoCanh] = i; DanhDau[i] = 1; TimKiem(SoCanh+1); //Tìm kiếm đỉnh tiếp theo L[SoCanh] = 0; DanhDau[i] = 0; } } } /*Chương trình chính*/ void main() { clrscr(); Doc_File(); KhoiTao(); cout<<"Duong di tu "<<D+1<<" den "<<C+1; TimKiem(1); if(Dem==0) cout<<" khong co"; delete*A,DanhDau,L; getch(); } Biên Soạn: Đào Anh Pha Trang 24 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 5 Một lưới giao thơng hai chiều giữa n địa điểm được cho bởi ma trận A[i,j] trong đĩ A[i,j]=1 nếu cĩ đường đi từ i đến j, cịn A[i,j] = 0 trong trường hợp ngược lại. Một người đưa thơ cần đi qua tất cả các con đường này để phát thơ, mỗi đường chỉ qua một lần. Hãy xác định một lộ trình của người đưa thơ này (cĩ thể tồn tại nhiều lộ trình khác nhau) hay thơng báo khơng tồn tại đường như vậy. Dữ liệu vào: cho trong file Bai5.inp. - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: In ra màn hình đường đi của người đưa thơ (nếu cĩ). Ví dụ: Bai5.inp Kết quả: 5 1->2->3->4->2->5->4 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 Bai5.inp Kết quả: 5 KHONG TON TAI DUONG DI 0 1 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 Bai5.inp Kết quả: 5 2->1->5->4->2->3->4 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 HƯỚNG DẪN THUẬT TỐN Bài tốn 5 chính là bài tốn tìm đường đi Euler. Điều kiện để cĩ đường đi Euler là: - Đồ thị liên thơng. - Đồ thị cĩ khơng quá 2 đỉnh bậc lẻ. Nếu cĩ 2 đỉnh bậc lẻ thì đỉnh xuất phát tìm đường đi phải là đỉnh bậc lẻ. Biên Soạn: Đào Anh Pha Trang 25 Giáo Trình Thực Hành Lý Thuyết Đồ Thị Ý tưởng thuật tốn: Sử dụng kỹ thuật xố cạnh. Nghĩa là, khi ta đi qua bất kỳ cạnh nào ta phải xố cạnh tương ứng bằng cách gán trọng số đường đi của cạnh mới đi qua bằng 0. Thuật tốn kết thúc khi ta đi qua tất cả các cạnh của đồ thị khi đĩ ma trận trận liên kết của đồ thị bằng 0. HƯỚNG DẪN CÀI ĐẶT ¾ Cài đặt hàm kiểm tra tính liên thơng của đồ thị nếu liên thơng trả về kết quả 1 ngược lại trả về kết quả 0. ¾ Cài đặt hàm kiểm tra đồ thị cĩ thỏa mãn tồn tại khơng quá 2 đỉnh bậc lẻ nếu thỏa mãn trả về kết quả 1 ngược lại trả về kết quả 0. Nếu tồn tại đỉnh bậc lẻ thì đỉnh bậc lẻ chính là đỉnh xuất phát và trong quá trình kiểm tra chúng ta đếm luơn số cạnh của đồ thị. Bởi vì thuật tốn kết thúc khi ta đi hết tất cả mọi cảnh của đồ thị. ¾ Cài đặt thuật tốn tìm đường đi Euler: trước tiên kiểm tra xem đồ thị co thỏa mãn điều kiện tồn tại đường đi Euler hay chưa nếu khơng thỏa mãn thì thuật tốn kết thúc. Ngược lại ta tìm đường đi Euler như sau: - Chọn đỉnh xuất phát: nếu tồn tại đỉnh bậc lẻ thì chọn đỉnh bậc lẻ làm đỉnh xuất phát, nếu khơng tồn tại đỉnh bậc lẻ thì chọn 1 đỉnh bất kỳ thơng thường ta chọn đỉnh 1 làm đỉnh xuất phát. - Từ đỉnh xuất phát ta đi tới đỉnh kề nĩ và xĩa cạnh tương ứng. Nếu j là đỉnh kề với đỉnh xuất phát thì A[xuất phát][j]= A[j][xuất phát] = 0 và đỉnh xuất phát ta gán bằng đỉnh j. Lặp lại cho đến khi khơng cịn đi được nữa (đi qua mọi cạnh của đồ thị) thì thuật tốn kết thúc. CHƯƠNG TRÌNH MẪU #include #include #include #include #define TenFile "Bai5.inp" /*Dọc dữ liệu của bài tốn*/ void Doc_File(int **A,int &n) { FILE*f = fopen(TenFile,"rb"); fscanf(f,"%d",&n); *A = new int [n]; cout<<"Ma Tran Lien Ket Cua Do Thi"; for(int i =0;i<n;i++) { A[i] = new int [n]; cout<<endl; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); Biên Soạn: Đào Anh Pha Trang 26 Giáo Trình Thực Hành Lý Thuyết Đồ Thị cout<<" "<<A[i][j]; } } fclose(f); } /*Kiểm tra tính liên thơng của đồ thị. Đồ thị liên thơng thì hàm trả về giá trị 1, ngược lại hàm trả về giá trị 0.*/ char LienThong(int **A,int n) { char*DanhDau = new char [n]; char ThanhCong; int Dem=0; for(int i = 0; i<n; i++) DanhDau[i] = 0; DanhDau[0] = 1; Dem++; do { ThanhCong =1; for(i = 0; i<n; i++) if(DanhDau[i]==1) { for(int j = 0; j<n; j++) if (DanhDau[j] == 0 && A[i][j] > 0) { DanhDau[j] = 1; ThanhCong =0; Dem++; if(Dem == n) return 1; } } }while (ThanhCong == 0); return 0; } /*Kiểm tra đồ thị cĩ quá 2 đỉnh bậc lẻ hay khơng. Nếu quá 2 đỉnh bậc lẻ hàm trả về giá trị 0, ngược lại hàm trả về giá trị 1. Tìm đỉnh xuất phát lưu trong biến XP và tổng số cạnh lưu trong biến Canh*/ char KiemTraBacLe(int**A, int n,int &XP, int &Canh) { int BacDinh,BacLe=0; Canh = 0; XP = 0; for(int i = n-1; i>=0; i--) { BacDinh = 0; for(int j = 0; j<n; j++) if(A[i][j]>0) BacDinh++; Biên Soạn: Đào Anh Pha Trang 27 Giáo Trình Thực Hành Lý Thuyết Đồ Thị if(BacDinh%2==1) { XP= i; BacLe++; } Canh+=BacDinh; } Canh = Canh/2; if(BacLe>2) return 0; else return 1; } /*Tim mot duong di Euler*/ void Euler(int**A,int n){ int XuatPhat,SoCanh,Dem; int *LuuDuong; if(LienThong(A,n)==1 && KiemTraBacLe(A,n,XuatPhat,SoCanh)==1){ LuuDuong = new int[SoCanh+1]; LuuDuong[0] = XuatPhat; Dem = 1; do{ int j = 0; while(A[XuatPhat][j]==0) j++; A[XuatPhat][j] = A[j][XuatPhat] = 0; LuuDuong[Dem] = XuatPhat = j; Dem++; }while(Dem<=SoCanh); cout<<"\nDuong Di Cua Nguoi Dua Tho:\n"<<LuuDuong[0]+1; for(int i = 1; i<=SoCanh; i++) cout "<<LuuDuong[i]+1; }else cout<<"\nKhong ton tai duong di."; } /*Chương trình chính*/ void main() { clrscr(); int **A,n; Doc_File(A,n); Euler(A,n); delete*A; getch(); } Biên Soạn: Đào Anh Pha Trang 28 Giáo Trình Thực Hành Lý Thuyết Đồ Thị CẢI TIẾN THUẬT TỐN XỬ LÝ CÁC TRƯỜNG HỢP ĐẶC BIỆT 1. Trường hợp đồ thị cĩ 2 đỉnh bậc lẻ trong đĩ cĩ 1đỉnh bậc 1. Xét đồ thị: Nếu chúng ta xuất phát từ đỉnh 4. Khi chúng ta đi 4->2->1 đồ thị của ta sẽ tương ứng với thuật tốn xố cạnh là: Khi đĩ điểm xuất phát của ta sẽ bắt đầu từ đỉnh 1, tại đỉnh này chúng ta sẽ khơng cịn đường đi nữa vì nĩ là đỉnh cơ lập. Để khắc phục được hiện trạng này chúng ta phải chọn ưu tiên đỉnh xuất phát là đỉnh cĩ bậc 1 và đỉnh kết thúc sẽ là đỉnh bậc lẻ cịn lại. Bai5.inp Kết quả: 6 4->2->5->1->3->5->6->2 0 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 Hàm cải tiến kiểm tra đỉnh bậc lẻ và chon đỉnh xuất phát. char KiemTraBacLe(int**A, int n,int &XP, int &Canh) { int BacDinh,BacLe=0,T=0; Canh = XP = 0; for(int i = 0; i<n; i++) { BacDinh = 0; for(int j = 0; j<n; j++) if(A[i][j]>0) BacDinh++; if(BacDinh%2==1) { if(BacDinh==1) { T = 1; XP= i; } Biên Soạn: Đào Anh Pha Trang 29 Giáo Trình Thực Hành Lý Thuyết Đồ Thị if(T = 0) XP = i; BacLe++; } Canh+=BacDinh; } Canh = Canh/2; if(BacLe>2) return 0; else return 1; } 2. Trường hợp đồ thị cĩ 2 đỉnh bậc lẻ trong đĩ cĩ 2 đỉnh bậc 1. Xử lý tương tự như trường hợp 1 nhưng ta phải lưu vết đường đi đã đi qua để tránh trường hợp đường đi sau khi xĩa thì đỉnh tương ứng xuất phát là đỉnh cơ lập. Cĩ nhiều cách để lưu vết, tìm kiếm bằng phương pháp đệ quy là một trong những cánh lưu vết hiệu quả và đơn giản. Tuy nhiên đồ phức tạp của thuật tốn quá lớn nên trong thực tế người ta ích sử dụng phương pháp này. 3. Kỹ thuật tìm kiếm đệ quy tìm đường đi Euler. #include #include #include #define Filename "Bai5.inp" /*Khai báo các biến tồn cục*/ int Dem = 0; //Đếm số đường đi int*L; //Lưu lại đỉnh đã đi int **A,n int XuatPhat=0; //Đỉnh xuẩt phát tìm kiếm là đỉnh bậc lẻ nếu đồ thị cĩ đỉnh bậc lẻ int SoCanh=0; //Lưu số cạnh của đồ thị vì đường đi đi qua tất cả các cạnh /*Dọc file dữ liệu và khởi tạo ban đầu*/ void Doc_File(){ int BacDinh; FILE*f = fopen(Filename,"rb"); fscanf(f,"%d",&n); cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<n<<endl; *A = new int [n]; for(int i =0;i<n;i++) { A[i] = new int [n]; BacDinh = 0; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" "; Biên Soạn: Đào Anh Pha Trang 30 Giáo Trình Thực Hành Lý Thuyết Đồ Thị if(A[i][j] == 1) BacDinh++; } if(BacDinh%2==1) XuatPhat = i; //Xuẩt phát là đỉnh bậc lẻ SoCanh+=BacDinh; cout<<endl; } fclose(f); SoCanh = SoCanh/2; //Số cạnh = tổng bậc /2 L = new int [SoCanh+1]; //Khởi tạo lưu đỉnh L[0] = XuatPhat; } /*Xuất đường đi tìm được ra màn hình*/ void InDuongDi() { Dem++; cout<<endl<<XuatPhat+1; for (int i = 1; i<=SoCanh; i++) cout "<<L[i]+1; } /*Thủ tục tìm kiếm đệ quy*/ void TimKiem(int Canh) { /*Tìm cho đến khi cạnh tìm được lớn hơn số cạnh của đồ thị mới xuất đường đi*/ if(Canh > SoCanh && Dem ==0 ) InDuongDi(); else { for(int i = 0; i<n; i++) if( A[L[Canh-1]][i]>0 && Dem==0){ L[Canh] = i; A[L[Canh-1]][i]=A[i][L[Canh-1]]=0; //Xĩa cạnh TimKiem(Canh+1); //Tìm đỉnh tiếp theo A[L[Canh-1]][i]=A[i][L[Canh-1]]=1; //Phục hồi cạnh L[Canh] = 0; } } } void main() { Doc_File(); cout<<"\nDUONG DI"; TimKiem(1); if(Dem==0) cout<<" KHONG CO"; delete*A,L; getch(); } Biên Soạn: Đào Anh Pha Trang 31 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 6 Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n, mỗi thành phố người khách chỉ muốn đi qua chúng một lần. Mạng lưới giao thơng giữa n thành phố là hai chiều và được cho bởi ma trận A[i,j] trong đĩ A[i,j] =1 nếu cĩ đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại. Hãy viết chương trình thiết lập cho người khách một lộ trình (cĩ thể tồn tại nhiều lộ trình) hay thơng báo khơng tồn tại lộ trình theo yêu cầu của khách. Dữ liệu vào: cho trong file Bai6.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng 2 ghi đỉnh mà người khách du lịch xuất phát. - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: In ra màn hình đường đi của người khách (nếu cĩ). Ví dụ: Bai6.inp Kết quả: 5 1->2->3->4->5 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 Bai6.inp Kết quả: 6 KHONG TON TAI DUONG DI 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 Bai6.inp Kết quả: 5 2->1->5->4->3 2 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 Biên Soạn: Đào Anh Pha Trang 32 Giáo Trình Thực Hành Lý Thuyết Đồ Thị Bai6.inp Kết quả: 6 KHONG TON TAI DUONG DI 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 HƯỚNG DẪN THUẬT TỐN Sử dụng kỹ thuật tìm kiếm theo chiều sâu. HƯỚNG DẪN CÀI ĐẶT Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy. CHƯƠNG TRÌNH MẪU #include #include #include #define FileIn "Bai6.inp" int Dem = 0; //Dếm số đường đi int*L; //Lưu lại đường đi char*DanhDau; //Dánh dấu đỉnh đã đi int **A,n,D; /*Dọc file dữ liệu bài tốn*/ void Doc_File() { FILE*f = fopen(FileIn,"rb"); fscanf(f,"%d%d",&n,&D); cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<endl; *A = new int [n]; for(int i =0;i<n;i++) { A[i] = new int [n]; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" "; } cout<<endl; } fclose(f); D--; } /*Khởi tạo dữ liệu ban đầu cho bài tốn*/ void KhoiTao() { Biên Soạn: Đào Anh Pha Trang 33 Giáo Trình Thực Hành Lý Thuyết Đồ Thị DanhDau = new char [n]; L = new int [n]; for (int i = 0; i<n; i++) { DanhDau[i] = 0; L[i] = 0; } DanhDau[D] = 1; L[0] = D; } /*In đường đi của bài tốn ra màn hình*/ void InDuongDi(int Dinh) { Dem++; cout<<endl<<D+1; for (int i = 1; i<Dinh; i++) cout "<<L[i]+1; } /*Tìm kiếm đường đi*/ void TimKiem(int Dinh) { if(Dinh == n && Dem == 0) InDuongDi(Dinh); else { for(int i = 0; i<n; i++) if( A[L[Dinh-1]][i]>0 && DanhDau[i] == 0 && Dem==0){ L[Dinh] = i; DanhDau[i] = 1; TimKiem(Dinh+1); //Tiếm kiếm đỉnh kế tiếp L[Dinh] = 0; DanhDau[i] = 0; } } } /*Chương trình chính*/ void main() { clrscr(); Doc_File(); KhoiTao(); cout<<"Duong Di Nguoi Khach"; TimKiem(1); //Tìm kiếm từ đỉnh thứ 2 của đồ thị if(Dem==0) cout<<" Khong Co"; delete*A,DanhDau,L; getch(); } Biên Soạn: Đào Anh Pha Trang 34 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 7 Cĩ n thành phố biết rằng đường đi giữa các thành phố (nếu cĩ) là đường đi hai chiều. Sơ đồ mạng lưới giao thơng của n thành phố cho bởi ma trận A[i,j] trong đĩ: - A[i,j] là độ dài đường đi từ thành phố i đến thành phố j. - A[i,j] = 0 nếu khơng cĩ đường đi từ thành phố i đến thành phố j. - A[i,j] = A[j,i] - A[i,j] nguyên, khơng âm. Hãy xác định đường đi ngắn nhất từ thành phố D đến thành phố C. Dữ liệu vào: đồ thị đã liên thơng và cho trong file Bai7.inp với nội dung - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng thứ hai lưu đỉnh D và đỉnh C. - Dịng i+2 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: xuất ra màn hình đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được. Ví dụ: Bai7.inp Kết quả: 6 DUONG DI NGAN NHAT LA: 5 1 6 1->2->4->6 0 1 2 0 0 0 1 0 2 2 3 0 2 2 0 5 4 0 0 2 5 0 3 2 0 3 4 3 0 4 0 0 0 2 4 0 Bai7.inp Kết quả: 6 DUONG DI NGAN NHAT LA: 8 1 6 1->2->4->6 0 1 4 0 0 0 1 0 2 6 5 0 4 2 0 7 3 0 0 6 7 0 0 1 0 5 3 0 0 3 0 0 0 1 3 0 HƯỚNG DẪN THUẬT TỐN Sử dụng thuật tốn DIJKSTRA tìm đường đi ngắn nhất. Biên Soạn: Đào Anh Pha Trang 35 Giáo Trình Thực Hành Lý Thuyết Đồ Thị CHƯƠNG TRÌNH MẪU #include #include #include #include #define FileIn "Bai7.inp" /*Đọc file dữ liệu bài tốn*/ void Doc_File(int**A, int &n, int &D, int &C){ FILE*f = fopen(FileIn,"rb"); fscanf(f,"%d%d%d",&n,&D,&C); cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl; *A = new int [n]; for(int i =0;i<n;i++) { A[i] = new int [n]; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" "; } cout<<endl; } fclose(f); D--; C--; } /*Thuật tốn Dijkstra tìm đường đi ngắn nhẩt từ đỉnh D đến đỉnh C*/ void Dijkstra(int **A, int n, int D, int C) { char *DanhDau = new char[n]; int *Nhan = new int[n]; int *Truoc = new int[n]; int XP, min; for(int i=0; i<n; i++){ Nhan[i] = MAXINT; DanhDau[i] = 0; Truoc[i] = D; } Biên Soạn: Đào Anh Pha Trang 36 Giáo Trình Thực Hành Lý Thuyết Đồ Thị Nhan[D] = 0; DanhDau[D] = 1; XP = D; while(XP != C){ for(int j=0; j<n; j++) if(A[XP][j]>0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) { Nhan[j] = A[XP][j]+Nhan[XP]; Truoc[j] = XP; } min = MAXINT; for(j = 0; j<n; j++) if(min>Nhan[j]&& DanhDau[j]==0){ min = Nhan[j] ; XP = j ; } DanhDau[XP] = 1; } cout<<”Duong Di Ngan Nhat La:”<<Nhan[C]<<endl; cout<<C+1<<” <- “<<Truoc[C]+1; i = Truoc[C]; while(i!=D){ i = Truoc[i]; cout<<” <- “<<i+1; } } /*Chương trình chính*/ void main() { int**A,n,Dau,Cuoi; Doc_File(A,n,Dau,Cuoi); Dijkstra(A,n,Dau,Cuoi); delete*A; getch(); } Biên Soạn: Đào Anh Pha Trang 37 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 8 Một cơng ty cần thay tồn bộ hệ thống dây điện cho n phịng làm việc. Cho biết sơ đồ điện hiện cĩ của n căn phịng này được biều diễn bằng ma trận A[i,j] trong đĩ: - A[i,j]=A[j,i] chính là chiều dài dây điện nối liền giữa hai phịng i và j. - A[i,j] = A[j,i] = 0 nếu i khơng nối liền với j. Hãy lập trình tính độ dài cuả dây dẫn cần sử dụng sao cho cả n phịng điều cĩ điện và số lượng này là ít nhất. Chú ý: đồ thị đã cho là liên thơng. Dữ liệu vào: cho trong file Bai8.inp (đồ thị cho đã liên thơng). - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng i+1 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: lưu trong file Bai8.out với nội dung sau: - Dịng đầu lưu độ dài dây dẫn nhỏ nhất - Các dịng cịn lại lưu đường đi cần nối điện giữa đỉnh i nối với đỉnh j cĩ trọng số A[i,j] (i -> j = A[i][j]). Bai8.inp Bai8.out 5 0 3 3 2 2 3 0 2 3 8 3 2 0 1 4 2 3 1 0 4 2 8 4 4 0 7 4 – 3 3 – 2 4 – 1 1 – 5 Bai8.inp Bai8.out 8 0 2 3 4 0 0 0 0 2 0 3 0 4 0 0 0 3 3 0 7 6 5 2 0 4 0 7 0 0 0 3 0 0 4 6 0 0 4 0 8 0 0 5 0 4 0 1 6 0 0 2 3 0 1 0 5 0 0 0 0 8 6 5 0 20 1 - 2 1 - 3 3 - 7 7 - 6 7 - 4 2 - 5 7 - 8 HƯỚNG DẪN THUẬT TỐN ¾ Thuật tốn Prim tìm cây phủ tối tiểu. ¾ Thuật tốn Kruskal tìm cây phủ tối tiểu. 1) Thuật tốn Prim tìm cây phủ tối tiểu. Bước 1: Xuất phát từ đỉnh k bất kỳ (thơng thường chon k là đỉnh đầu tiên) chọn một cạnh cĩ trọng số nhỏ nhất của đồ thị (min{A[k][j]}j=1..n) ta đánh dấu 2 đỉnh đi qua cạnh Biên Soạn: Đào Anh Pha Trang 38 Giáo Trình Thực Hành Lý Thuyết Đồ Thị đĩ và số cạnh tìm được là 1. Chuyển sang bước 2. Bước 2: Tìm cạnh nhỏ nhất của đồ thị với điều kiện cạnh tìm được phải cĩ 1 đỉnh chưa đánh dấu và 1 đỉnh đã đánh dấu (min{A[i][j]}j=1..n, i=1..n sao cho i đánh đấu và j chưa đánh dấu) để tránh trường hợp tạo thành chu trình. Ta tăng số cạnh tìm được lên 1 và chuyển sang bước 3. Bước 3: Nếu số cạnh tìm được bằng n-1 kết thúc thuật tốn, ngược lại quay về bước 2. 2) Thuật tốn Kruskal tìm cây phủ tối tiểu. Bước 0: Khởi tạo tập cạnh tìm được là rỗng. Chuyển sang bước 1. Bước 1: Chọn một cạnh cĩ trọng số nhỏ nhất sao cho khi đưa cạnh này vào tập cạnh tìm được khơng tạo thành chu trình. Tăng số cạnh tìm được lên 1và chuyển sang bước 2. Bước 2: Nếu số cạnh tìm được bằng n-1 thuật tốn kết thúc, ngược lại quay về bước 1. HƯỚNG DẪN CÀI ĐẶT 1) Thuật tốn Prim tìm cây phủ tối tiểu. Ta tổ chức mảng 1 chiều D để đánh dấu . Nếu D[i]=1 đỉnh i được đánh dấu và D[i]=0 nếu i chưa được đánh dấu. Bước 1: Tìm min{A[i][j]}j=1..n, i=1..n. Sau đĩ gán D[i]=D[j]=1 (đánh dấu 2 đỉnh i,j) và cho số cạnh tìm được bằng 1 (Dem=1). Bước 2: Tìm min{A[i][j]}j=1..n, i=1..n với điều kiện D[i]=1 và D[j]=0. Sau đĩ gán D[j]=1 (đánh dấu đỉnh j vừa tìm được) và tăng số cạnh lên 1 (Dem++). Bước 3: Nếu Dem = n-1 thì thuật tốn kết thúc. 2) Thuật tốn Kruskal tìm cây phủ tối tiểu. Ta tổ chức mảng 1 chiều D để đánh dấu . Nếu D[i]=T thì đỉnh i thuộc vào cây thứ T, D[i] = 0 thì đỉnh i chưa thuộc vào cây. Bước 1: Tìm min{A[i][j]}j=1..n, i=1..n ngoại trừ điều kiện D[i]=D[j]≠0. Vì khi thỏa mãn điều kiện trên đỉnh i,j đã thuộc vào một cây do đĩ khi lấy thêm cạnh này chúng sẽ tạo thành chu trình. Đỉnh i,j tìm được thoả mãn một trong các trường hợp sau: - Nếu D[i]=D[j]=0, đỉnh i,j chưa thuộc vào cây nên khi lấy 2 đỉnh này vào tập cạnh ta cho chúng thuộc vào 1 cây mới. Nghĩa là số cây T++ và D[i]=D[j]=T. - Nếu D[i]=0 và D[j]≠0, đỉnh i chưa thuộc vào cây và j đã thuộc vào cây. Ta lấy đỉnh i vào cây tương ứng với cây của đỉnh j. Nghĩa là gán D[i]=D[j]. - Nếu D[i]≠0 và D[j]=0, đỉnh j chưa thuộc vào cây và i đã thuộc vào cây. Ta lấy đỉnh j vào cây tương ứng với cây của đỉnh i. Nghĩa là gán D[j]=D[i]. - Nếu D[i]≠D[j] và D[i]≠0 và D[j]≠0, đỉnh i thuộc vào cây và đỉnh j cũng thuộc vào cây nhưng cây i và j là 2 cây khác nhau. Ta tiến hành ghép cây nghĩa là ghép 2 cây chứa i,j thành 1 cây mới. Temp = D[i] for(int i=0 ; i<n ; i++) Biên Soạn: Đào Anh Pha Trang 39 Giáo Trình Thực Hành Lý Thuyết Đồ Thị if(D[i]==Temp) D[i]=D[j] Tăng số cạnh tìm được lên 1 (Dem++). Bước 2: Nếu Dem = n-1 thì thuật tốn kết thúc. Chú ý: trong qua trình tìm cĩ thể tạo thành rất nhiều cây nhưng kết quả tìm được cuối cùng là một cây thơng qua quá trình ghép cây. CHƯƠNG TRÌNH MẪU 1) Thuật tốn Prim tìm cây phủ tối tiểu. #include #include #include #include #define FileInt "Bai8.inp" #define FileOut "Bai8.out" /*Lưu lại những cạnh đã đi qua x->y*/ typedef struct Egde { int x,y; }; /*Doc dữ liệu từ file*/ void Doc_File(int **A,int &n){ FILE*f = fopen(FileInt,"rb"); fscanf(f,"%d",&n); *A = new int [n]; for(int i =0;i<n;i++) { A[i] = new int [n]; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); } } fclose(f); } /*Ghi dữ liệu ra file*/ void Ghi_File(Egde*L,int n,int Sum) { FILE*f = fopen(FileOut,"wb"); fprintf(f,"%d\n",Sum); for(int i =0; i<n-1; i++) fprintf(f,"%d - %d\n",L[i].x+1,L[i].y+1); fclose(f); } /*Thuật tốn Prim*/ Biên Soạn: Đào Anh Pha Trang 40 Giáo Trình Thực Hành Lý Thuyết Đồ Thị void Prim(int **A, int n){ char *D = new char[n]; /*Dánh dấu đỉnh*/ Egde *L = new Egde[n-1]; /*Lưu đường đi */ int min = MAXINT, Dem = 0, Sum = 0; /*Khoi tạo giá trị cho mảng đánh dấu*/ for(int i=0; i<n; i++) D[i]=0; /*Tìm cạnh nhỏ nhất đầu tiên xuất phát từ đỉnh 1*/ for(int j=1; j<n; j++) if(min>A[0][j] && A[0][j]!=0){ min = A[0][j]; L[0].y = j; } L[0].x = 0; D[0] = D[L[0].y] = 1; Sum+=min; Dem++; /*Thực hiện cho đến khi số cạnh tìm được là n-1 cạnh*/ do{ min = MAXINT; for( i=0; i<n; i++) if(D[i]==1) for( j=0; j<n; j++) if(A[i][j]>0 && min>A[i][j] && D[j]==0){ min = A[i][j]; L[Dem].x = i; L[Dem].y = j; } Sum+=min; D[L[Dem].y] = 1; Dem++; } while(Dem<n-1); Ghi_File(L,n,Sum); /*Ghi kết quả tìm được vào file*/ } /*Chương trình chính*/ void main() { int **A,n; Doc_File(A,n); Prim(A,n); delete *A; } Biên Soạn: Đào Anh Pha Trang 41 Giáo Trình Thực Hành Lý Thuyết Đồ Thị 2) Thuật tốn Kruskal tìm cây phủ tối tiểu. void Kruskal(int **A, int n){ char *D = new char[n]; Egde *L = new Egde[n-1]; int min, Dem = 0, Sum = 0, T = 0, Temp; for(int i=0; i<n; i++) D[i] = 0; do{ min = MAXINT; for( i=0; i<n; i++) for(int j=0; j<n; j++) if(A[i][j]>0 && min>A[i][j]&& !(D[i]!=0 && D[i]==D[j])) { min = A[i][j]; L[Dem].x = i; L[Dem].y = j; } /*Tạo ra cây mới*/ if(D[L[Dem].x] ==0 && D[L[Dem].y] == 0){ T++; D[L[Dem].x] = D[L[Dem].y] = T; } /*Đưa đỉnh tương ứng vào cây*/ if(D[L[Dem].x] == 0 && D[L[Dem].y] != 0) D[L[Dem].x] = D[L[Dem].y]; /*Đưa đỉnh tương ứng vào cây*/ if(D[L[Dem].x] != 0 && D[L[Dem].y] == 0) D[L[Dem].y] = D[L[Dem].x]; /*Ghép 2 cây thành 1 cây mới*/ if(D[L[Dem].x] != D[L[Dem].y] && D[L[Dem].y]!=0) { Temp = D[L[Dem].x]; for( i=0; i<n; i++) if(Temp==D[i]) D[i]=D[L[Dem].y]; } Sum+=min; Dem++; } while(Dem<n-1); Ghi_File(L,n,Sum); } Biên Soạn: Đào Anh Pha Trang 42 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 9 Cĩ n thành phố được đánh số từ 1 đến n. Mạng lưới giao thơng giữa các thành phố là đường hai chiều. Trên đường đi (nếu cĩ) từ thành phố i đến thành phố j, người ta khơng được mang quá A[i,j] đơn vị hàng. Nếu khơng cĩ đường đi từ thành phố i đến thành phố j thì xem như A[i,j] = 0. Cần vận chuyển hàng từ thành phố D đến thành phố C. Hãy thiết lập kế hoạch vận chuyển sao cho khối lượng hàng vận chuyển là nhiều nhất. Dữ liệu vào: đồ thị đã liên thơng và cho trong file Bai9.inp với nội dung - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng thứ hai lưu đỉnh D và đỉnh C. - Dịng i+2 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: xuất ra màn hình kế hoạch vận chuyển từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được. Ví dụ: Bai9.inp Kết quả: 6 KHOI LUONG VAN CHUYEN NHIEU NHAT LA: 2 1 6 1->3->4->6 0 1 2 0 0 0 1 0 2 2 3 0 2 2 0 5 4 0 0 2 5 0 3 2 0 3 4 3 0 4 0 0 0 2 4 0 Bai9.inp Kết quả: 6 KHOI LUONG VAN CHUYEN NHIEU NHAT LA: 3 1 6 1->3->4->2->5->6 0 1 4 0 0 0 1 0 2 6 5 0 4 2 0 7 3 0 0 6 7 0 0 1 0 5 3 0 0 3 0 0 0 1 3 0 Biên Soạn: Đào Anh Pha Trang 43 Giáo Trình Thực Hành Lý Thuyết Đồ Thị HƯỚNG DẪN THUẬT TỐN Sử dụng phương pháp tối ưu theo từng đỉnh giống thuật tốn DIJKSTRA. HƯỚNG DẪN CÀI ĐẶT Khởi tạo: - Mọi nhãn ban đầu bằng vơ cùng. - Tất cả các đỉnh chưa được đánh dấu - Trước mọi đỉnh là đỉnh đầu. - Đánh dấu đỉnh xuất phát. Xét đỉnh xuất phát là đỉnh XP: - Nếu A[XP][j]>0, j chưa được đánh dấu và Nhan[j] = vơ cùng thì: Nhan[j] = min{Nhan[XP],A[XP][j]} Truoc[j] = XP - Nếu A[XP][j]>0, j chưa được đánh dấu, Nhan[j] khác vơ cùng và min{Nhan[XP],A[XP][j]}>Nhan[j] thì: Nhan[j] = min{Nhan[XP],A[XP][j]} Trước[j] = XP Xét đỉnh xuất phát tiếp theo: Đỉnh xuất phát tiếp theo là đỉnh chưa được đánh dấu và nhãn của đỉnh phải lớn nhất nhưng khác vơ cùng. Khi chọn được đỉnh xuất phát ta phải đánh dấu đỉnh XP. Minh họa thuật tốn: Xét đồ thị dưới đây, hãy lập kế hoạch vận chuyển hàng nhiều nhất từ đỉnh 1 đến đỉnh 6. Khởi tạo: Đỉnh 1 2 3 4 5 6 Nhãn ∞ ∞ ∞ ∞ ∞ ∞ Đánh dấu 1* 0 0 0 0 0 Trước 1 1 1 1 1 1 Biên Soạn: Đào Anh Pha Trang 44 Giáo Trình Thực Hành Lý Thuyết Đồ Thị - Xuất phát là đỉnh 1: dánh dấu đỉnh 1. Đỉnh 1 2 3 4 5 6 Nhãn ∞ 1 2 ∞ ∞ ∞ Đánh dấu 1* 0 0 0 0 0 Trước 1 1 1 1 1 1 - Xuất phát là đỉnh 3: đánh dấu đỉnh 3 (đỉnh 3 là đỉnh cĩ nhãn lớn nhất khác vơ cùng và chưa được đánh dấu). Đỉnh 1 2 3 4 5 6 Nhãn ∞ 2 2 2 2 ∞ Đánh dấu 1 0 1* 0 0 0 Trước 1 3 1 3 3 1 - Xuất phát là đỉnh 2: đánh dấu đỉnh 2 (đỉnh 2 là đỉnh cĩ nhãn lớn nhất khác vơ cùng và chưa được đánh dấu). Đỉnh 1 2 3 4 5 6 Nhãn ∞ 2 2 2 2 ∞ Đánh dấu 1 1* 1 0 0 0 Trước 1 3 1 3 3 1 - Xuất phát là đỉnh 4: đánh dấu đỉnh 4 (đỉnh 4 là đỉnh cĩ nhãn lớn nhất khác vơ cùng và chưa được đánh dấu). Đỉnh 1 2 3 4 5 6 Nhãn ∞ 2 2 2 2 2 Đánh dấu 1 1 1 1* 0 0 Trước 1 3 1 3 3 4 - Xuất phát là đỉnh 5: đánh dấu đỉnh 5 (đỉnh 5 là đỉnh cĩ nhãn lớn nhất khác vơ cùng và chưa được đánh dấu). Đỉnh 1 2 3 4 5 6 Nhãn ∞ 2 2 2 2 2 Đánh dấu 1 1 1 1 1* 0 Trước 1 3 1 3 3 4 - Xuất phát là đỉnh 6: đánh dấu đỉnh 6. Đỉnh xuất phát bằng đỉnh đi đến nên thuật tốn kết thúc và trọng tải lớn nhất là 2, kế hoạch vận chuyển qua các con đường là: 6 — 4 — 3 — 1. Biên Soạn: Đào Anh Pha Trang 45 Giáo Trình Thực Hành Lý Thuyết Đồ Thị CHƯƠNG TRÌNH MẪU #include #include #include #include #define FileIn "Bai9.inp" /*Dọc file dữ liệu của bài tĩan*/ void Doc_File(int**A, int &n, int &D, int &C){ FILE*f = fopen(FileIn,"rb"); fscanf(f,"%d%d%d",&n,&D,&C); cout<<"Ma Tran Lien Ket Tuong Ung.\n"; cout<<D<<" "<<C<<endl; *A = new int [n]; for(int i =0;i<n;i++) { A[i] = new int [n]; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" "; } cout<<endl; } fclose(f); D--; C--; } /*Thủ tục tìm đường đi vận chuyển hàng nhiều nhất*/ void VanChuyen(int **A, int n, int D, int C) { char *DanhDau = new char[n]; int *Nhan = new int[n]; int *Truoc = new int[n]; int XP, min,max; for(int i=0; i<n; i++){ Nhan[i] = MAXINT; DanhDau[i] = 0; Truoc[i] = D; } DanhDau[D] = 1; XP = D; while(XP != C){ for(int j=0; j<n; j++) if(A[XP][j]>0&&DanhDau[j]==0){ Biên Soạn: Đào Anh Pha Trang 46 Giáo Trình Thực Hành Lý Thuyết Đồ Thị if(Nhan[j]==MAXINT){ if(Nhan[XP]>A[XP][j]) Nhan[j] = A[XP][j]; else Nhan[j] = Nhan[XP]; Truoc[j] = XP; } if(Nhan[j]!=MAXINT){ if(Nhan[XP]>A[XP][j]) min = A[XP][j]; else min = Nhan[XP]; if(Nhan[j]<min){ Nhan[j] = min; Truoc[j] =XP; } } } max = 0; for(j=0; j<n; j++) if(Nhan[j]<MAXINT&&DanhDau[j]==0&&max<Nhan[j]){ max = Nhan[j]; XP = j; } DanhDau[XP] = 1; } cout<<"Van chuyen nhieu nhat la: "<<Nhan[C]; cout<<"\nCon duong van chuyen nhu sau:\n"; cout<<C+1<<" <- "<<Truoc[C]+1; i = Truoc[C]; while(i!=D){ i = Truoc[i]; cout<<" <- "<<i+1; } } /*Chương trình chính*/ void main() { clrscr(); int**A,n,Dau,Cuoi; Doc_File(A,n,Dau,Cuoi); VanChuyen(A,n,Dau,Cuoi); delete*A; getch(); } Biên Soạn: Đào Anh Pha Trang 47 Giáo Trình Thực Hành Lý Thuyết Đồ Thị BÀI TỐN 10 Cĩ n thành phố biết rằng đường đi giữa các thành phố là đường đi hai chiều. Sơ đồ mạng lưới giao thơng của n thành phố cho bởi ma trận A[i,j] trong đĩ: - A[i,j] là độ dài đường đi từ thành phố i đến thành phố j. - A[i,j] = 0 nếu khơng cĩ đường đi từ thành phố i đến thành phố j. - A[i,j] = A[j,i] - A[i,j] nguyên, khơng âm. Hãy xác định đường đi dài nhất từ thành phố D đến thành phố C với điều kiện thành phố đã qua khơng được đi lại. Dữ liệu vào:đồ thị đã liên thơng và cho trong file Bai10.inp - Dịng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dịng thứ hai lưu đỉnh D và đỉnh C. - Dịng i+2 ( ) chứa n số A[i,1],A[i,2]A[i,n] mỗi số cách nhau bởi một khoảng trắng. ni ≤≤1 Dữ liệu ra: xuất ra màn hình đường đi dài nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được. Ví dụ: Bai10.inp Kết quả: 6 DUONG DI DAI NHAT LA: 16 1 6 1->2->4->3->5->6 0 1 2 0 0 0 1 0 2 2 3 0 2 2 0 5 4 0 0 2 5 0 3 2 0 3 4 3 0 4 0 0 0 2 4 0 Bai10.inp Kết quả: 6 DUONG DI DAI NHAT LA: 25 1 6 1->3->4->2->5->6 0 1 4 0 0 0 1 0 2 6 5 0 4 2 0 7 3 0 0 6 7 0 0 1 0 5 3 0 0 3 0 0 0 1 3 0 HƯỚNG DẪN THUẬT TỐN Sử dụng kỹ thuật tìm kiếm theo chiều sâu. Biên Soạn: Đào Anh Pha Trang 48 Giáo Trình Thực Hành Lý Thuyết Đồ Thị HƯỚNG DẪN CÀI ĐẶT Sử dụng kỹ thuật cài đặt tìm kiếm theo phương pháp đệ quy, khi tìm được 1 phương án thì lưu lại trạng thái của phương án ban đầu và so sánh với phương án mới tìm được, nếu phương án mới tốt hơn thì chọn phương án mới. CHƯƠNG TRÌNH MẪU include #include #include #define Filename "Bai10.inp" /*Khai báo các biến tồn cục*/ int*L,*L1; //Luu lai duong da di char*DanhDau; //Danh dau dinh da di int **A,n,D,C,Tong,Tong1,Canh1; /*Dọc file dữ liệu của bài tốn*/ void Doc_File() { FILE*f = fopen(Filename,"rb"); fscanf(f,"%d%d%d",&n,&D,&C); cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl; *A = new int [n]; for(int i =0;i<n;i++) { A[i] = new int [n]; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" "; } cout<<endl; } fclose(f); D--; C--; } /*Khởi tạo ban đầu cho thủ tục tìm kiếm*/ void KhoiTao() { DanhDau = new char [n]; L = new int [n]; //Lưu đường đi tìm được L1 = new int [n]; //Lưu đường đi lớn nhất for (int i = 0; i<n; i++) { DanhDau[i] = 0; //Các đỉnh chưa được đánh dấu L[i] = 0; } DanhDau[D] = 1; //Dánh dấu đỉnh xuẩt phát L[0] = D; //Đường đi đầu tiên qua đỉnh đầu Biên Soạn: Đào Anh Pha Trang 49 Giáo Trình Thực Hành Lý Thuyết Đồ Thị Tong = 0; //Trong số đường đi Tong1 = 0; //Lưu lại trọng số lớn nhất của đường đi } /*In đường đi dài nhất tìm được*/ void InDuongDi() { cout<<"\nDUONG DI DAI NHAT:"<<Tong1<<endl<<D+1; for (int i = 1; i<Canh1; i++) cout "<<L1[i]+1; } /*Xử lý để lấy phương án tổt hơn*/ void XuLy(int Canh) { if(Tong>Tong1){ Tong1 = Tong; //Lưu lại trọng số tốt hơn Canh1 = Canh; //Lưu lại số cạnh đã đi qua for(int i =0; i<Canh; i++) L1[i] = L[i]; //Lưu lại đường đi tốt hơn } } /*Thủ tục tìm kiếm đệ quy*/ void TimKiem(int SoCanh) { if(L[SoCanh-1] == C) XuLy(SoCanh); else { for(int i = 0; i<n; i++) if( A[L[SoCanh-1]][i]>0 && DanhDau[i] == 0){ L[SoCanh] = i; DanhDau[i] = 1; Tong+=A[L[SoCanh-1]][i]; TimKiem(SoCanh+1); L[SoCanh] = 0; Tong-=A[L[SoCanh-1]][i]; DanhDau[i] = 0; } } } void main() { Doc_File(); KhoiTao(); TimKiem(1); if(Tong1==0) cout<<"\NKHONG CO DUONG DI"; else InDuongDi(); delete*A,DanhDau,L; getch(); } Biên Soạn: Đào Anh Pha Trang 50 Giáo Trình Thực Hành Lý Thuyết Đồ Thị THUẬT TỐN [] Kiểm tra tính liên thơng của đồ thị .............................................................................. [] Đếm số thành phần liên thơng của đồ thị .................................................................... [] Thuật tốn tìm mọi đường đi từ đỉnh D đến đỉnh C .................................................... [] Thuật tốn tìm một đường đi Euler.............................................................................. [] Thuật tốn tìm một đường đi Hamilton ....................................................................... [] Thuật tốn Dijkstra tìm đường đi ngắn nhất ................................................................ [] Thuật tốn Prim tìm cây phủ tối tiểu ........................................................................... [] Thuật tốn Kruskal tìm cây phủ tối tiểu ...................................................................... [] Thuật tốn đệ quy tìm mọi đường đi Euler.................................................................. [] Thuật tốn đệ quy tìm mọi đường đi Hamilton ........................................................... [] Thuật tốn tốn khử đệ quy tìm mọi đường đi Euler................................................... [] Thuật tốn tốn khử đệ quy tìm mọi đường đi Hamilton ............................................ Biên Soạn: Đào Anh Pha Trang 51