BTVN — CS12.3 đồ thị, DFS, BFS. Dữ liệu và địa điểm giả định.
Giải nén đủ 9 tệp cùng thư mục. Cần Python 3; không cần thư viện cài thêm.
Mở demo.py bằng IDLE và Run Module hoặc chạy python demo.py.
Mở xe_dap.py để nhập s t như 0 5,0 6,2 2,5 0; q để thoát.
Đỉnh đánh số 0..6. ten_nha.inp lưu 7 nhãn khác nhau, đúng thứ tự chỉ số.
Các chương trình đọc tệp từ thư mục chứa mã, không phụ thuộc thư mục dòng lệnh.
canh.inp: số đỉnh rồi mỗi dòng một cặp u v; mỗi cạnh vô hướng ghi một lần.
ma_tran.inp: số đỉnh rồi n hàng, mỗi hàng n số 0/1 tách bằng khoảng trắng.
ke.inp: số đỉnh rồi n hàng; đầu hàng là chỉ số đỉnh; hàng biệt lập chỉ ghi chỉ số ấy.
tien_quyet.inp là có hướng: i j nghĩa muốn học i phải học j trước.
Chỉ dùng đơn đồ thị; không khuyên/cạnh trùng/chỉ số ngoài phạm vi.
Các bộ đọc ma trận và danh sách kề dùng được có hướng; vô hướng cần đủ hai chiều.
Kết quả: ba tệp khớp True; bậc [2,3,2,2,3,2,0]; DFS [0,1,3,5,4,2];
DFS stack [0,2,4,5,3,1]; BFS [0,1,2,3,4,5]; dist [0,1,1,2,2,3,-1].
0 đến5: [0,1,3,5],3 cạnh;0 đến6 không có đường;2 đến2 có 0 cạnh.
Hai thành phần {0,1,2,3,4,5} và {6}; đồ thị vô hướng mẫu có chu trình.
Tiên quyết ban đầu không chu trình; thêm 0->4 trong demo cho [0,4,3,1,0].
BFS dùng Q và head để giữ FIFO, không xóa đầu list. DFS stack dùng LIFO.
Các thuật toán đệ quy dùng cho đồ thị nhỏ của bài. Không dùng mẫu làm chỉ dẫn đường thật.
Lưu bản sao trước khi sửa; chương trình không ghi thay đổi vào các tệp đầu vào.
