1. Học hỏi
    2. /
  2. Khoa Học
    3. /
  3. Nhập môn Phân tích Mạng bằng Python
Connected

Bài tập

Đường đi ngắn nhất I

Bạn có thể tận dụng hiểu biết về cách tìm hàng xóm để thử tìm đường đi trong một mạng. Một thuật toán để tìm đường giữa hai nút là thuật toán "tìm kiếm theo chiều rộng" (breadth-first search, BFS). Với BFS, bạn bắt đầu từ một nút cụ thể và lặp qua các láng giềng của nó rồi đến láng giềng của các láng giềng, cho đến khi tìm thấy nút đích.

Các thuật toán tìm đường rất quan trọng vì chúng cung cấp một cách khác để đánh giá mức độ quan trọng của nút; bạn sẽ thấy điều này trong một bài tập sau.

Trong bộ 3 bài tập này, bạn sẽ xây dựng dần dần để đến thuật toán BFS hoàn chỉnh. Bài toán được chia thành 3 phần; nếu bạn thực hiện lần lượt, bạn sẽ có được bản cài đặt lần đầu của thuật toán BFS.

Hướng dẫn

100 XP
  • Tạo một hàm gọi là path_exists() với 3 tham số - G, node1 và node2 - và trả về việc có tồn tại đường đi giữa hai nút hay không.
  • Khởi tạo hàng đợi các nút cần thăm bằng nút đầu tiên, node1. queue nên là một danh sách.
  • Lặp qua các nút trong queue.
  • Lấy các láng giềng của nút bằng phương thức .neighbors() của đồ thị G.
  • Kiểm tra xem nút đích node2 có nằm trong tập neighbors hay không. Nếu có, trả về True.