NenTang.vn
Ngôn ngữ lập trìnhLập trình C++ nâng cao - Cấu trúc dữ liệu và Giải thuật
Lab 3.2 - Tìm đường đi bằng cách duyệt cây theo chiều rộng BFS (Breadth First Search)
Lý thuyết đồ thị
Thời lượng: 101 phútĐọc khoảng: 3 phút
Danh mục hình và bảng
Từ viết tắt
Nội dung bài học không khai báo từ viết tắt bằng thẻ abbr.
Nội dung bài học
Đề bài
Cho đồ thị có hướng G=<V,E> được biểu diễn dưới dạng danh sách cạnh. Hãy viết chương trình thực hiện tìm đường đi bằng cách sử dụng giải thuật BFS.Input
- Dòng đầu tiên chứa 2 số n, m là số đỉnh và số cạnh của đồ thị (1 <= n <= 1000, 1 <= m <= n*(n-1)/2).
- M dòng tiếp theo, mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị (1 <= u, v <= n). Các cạnh được liệt kê theo thứ tự tăng dần của các đỉnh đầu.
Output
- Biết rằng tồn tại ít nhất một đường đi từ tới , hãy chỉ ra đường đi đơn qua ít cung nhất. Nếu có nhiều đường đi đơn cùng qua ít cung nhất, hãy chỉ ra đường đi có thứ tự từ điển nhỏ nhất trong sốđó.
| Input | Output |
|
typescript |
typescript |
Giải
- Source code:
cpp

