Bài thực hành 1: Tìm kiếm mù

Nội dung:
Cho đồ thị vô hướng biểu diễn bởi ma trận kề trong tập tin dothi.inp với cấu trúc như sau:
o Dòng đầu tiên ghi số đỉnh đồ thị N
o dòng tiếp theo, dòng thứ ighi số nguyên , trong đó: NN],[jiA1],[=jiA nếu có cạnh nối giữa hai đỉnh ),1(,jjiji≤≤, và trong trường hợp ngược lại, mỗi số cách nhau bằng một ký tự tab. 0],[=jiA
Ví dụ:
1 2 3 4 Tập tin dothi.inp 4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0
Viết chương trình thực hiện các yêu cầu sau:
1. Nhập vào 2 đỉnh . Hãy in ra đường đi (thứ tự đỉnh) giữa và bằng tìm kiếm theo chiều rộng. vu,uv
2. Như câu 2, sử dụng thuật toán tìm kiếm theo chiều sâu. Lưu ý: dùng stack, không dùng đệ quy (tức là: hàm gọi lại chính nó).
Artificial Intelligence (03/2007) Nguyễn Anh Tuấn
Khoa CNTT - ĐH KHTN Tp. HCM
2
3. Cho biết đồ thị có bao nhiêu thành phần liên thông, và in ra danh sách đỉnh ứng với từng thành phần. Yêu cầu cài đặt bằng cả 2 phương pháp: tìm kiếm theo chiều rộng, tìm kiếm theo chiều sâu.

ngày 24/4/2007 nộp