Câu hỏi:
04/10/2024 30Nêu một ứng dụng của một trong hai thuật toán duyệt đồ thị đã học
Sách mới 2k7: 30 đề đánh giá năng lực DHQG Hà Nội, Tp. Hồ Chí Minh, BKHN 2025 mới nhất (600 trang - chỉ từ 160k).
Quảng cáo
Trả lời:
Hai thuật toán duyệt đồ thị theo chiều rộng (BFS) và chiều sâu (DFS) là hai thuật toán cơ bản nhất của đồ thị. Các thuật toán này giúp chúng ta “đến thăm” tất cả các cạnh và các đỉnh của đồ thị trong thời gian tối thiểu. Một số bài toán như: Kiểm tra một đồ thị là phân đôi (bi-partite), Tìm đường ngắn nhất trong đồ thị không có trọng số (Single source Shortest path in an unweighted graph), Tìm vòng trong đồ thị vô hướng, Tìm vòng (cycle) trong đồ thị có hướng, Case study: Dò mìn (Minesweeper).
Đã bán 152
Đã bán 114
Đã bán 132
Đã bán 47
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Tìm đường đi bằng thuật toán duyệt đô thị theo chiều rộng
Yêu cầu: Bản đồ mô tả đường đi giữa các địa điểm du lịch trong một thành phố được biểu diễn như ở Hình 1. Dựa vào thuật toán duyệt đồ thị theo chiều rộng được biểu diễn bằng ma trận kể, em hãy viết chương trình tìm đường đi từ địa điểm A đến địa điểm D sao cho đi qua ít địa điểm nhất.
Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
Dữ liệu ra: Các đỉnh của đường đi từ đỉnh A đến đỉnh D.
Câu 2:
Chương trình tìm đường đi bằng thuật toán duyệt đô thị theo chiều sâu
Yêu cầu: Cho đồ thị G. Hãy viết chương trình tìm đường đi từ đỉnh u đến đỉnh v bằng thuật toán duyệt đồ thị theo chiều sâu. Đồ thị G được biểu diễn bằng danh sách kể.
Dữ liệu vào:
- Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
– Đỉnh u và đỉnh v của đường đi.
Dữ liệu ra:
– Nếu có đường đi từ đỉnh u đến đỉnh v thì hiển thị các đỉnh của đường đi này. – Nếu không có đường đi thì hiển thị "Không có đường đi".
Câu 3:
Tìm đường di bằng thuật toán duyệt đồ thị theo chiều sâu
Yêu cầu; Cho bản đó (Hình 2) gồm các thành phố M, N, P, Q, R được biểu diễn bởi đồ thị. Dựa vào thuật toán duyệt đồ thị theo chiều sâu được biểu diễn bằng ma trận kể, viết chương trình in ra màn hình đường đi từ thành phố M đến thành phố R.
Dữ liệu vào: Tệp dothitxt chứa dữ liệu của đô thị. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn. Dữ liệu ra: Các dỉnh của đường di từ dỉnh M đến dỉnh R
Câu 4:
Nhiệm vụ. Đếm số thành phần liên thông của đồ thị
Một đô thị G được gọi là không liên thông nếu tổn tại đỉnh u và đỉnh v thuộc G mà không có đường đi giữa hai đỉnh này. Khi đó, đỉnh u và đỉnh v thuộc hai thành phần liên thông khác nhau. Nếu tồn tại đường đi giữa đỉnh u và đỉnh v thì hai đỉnh này phải thuộc cùng một thành phần liên thông. Như vậy, đô thị G không liên thông sẽ có ít nhất hai thành phần liên thông. Yêu cầu: Cho đồ thị vô hướng G được biểu diễn bằng danh sách kể. Hãy viết chương trình cho biết số thành phần liên thông của đô thị G.
Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đô thị G. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cạnh gồm hai đỉnh.
Dữ liệu ra: Số thành phần liên thông của đô thị G.
Dữ liệu vào dữ liệu ra tương ứng với đồ thị G1 như sau:
Câu 5:
Nhiệm vụ 1. Chương trình tìm đường đi bằng thuật toán duyệt đồ thị theo chiều rộng
Yêu cầu: Cho đồ thị vô hướng G. Hãy viết chương trình tìm đường đi từ đỉnh u đến đỉnh v bằng thuật toán duyệt đồ thị theo chiều rộng. Đô thị G được biểu diễn bằng danh sách kể. Dữ liệu vào:
- Tệp dothi.txt chứa dữ liệu của đồ thị. Hàng đầu tiên là danh sách các đỉnh của đồ thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.
– Đỉnh u và đỉnh v của đường đi.
Dữ liệu ra:
– Nếu có đường đi từ đỉnh u đến đỉnh v thì hiển thị các đỉnh của đường đi này. – Nếu không có đường đi thì hiển thị "Không có đường đi".
Gọi 084 283 45 85
Hỗ trợ đăng ký khóa học tại Vietjack
về câu hỏi!