Bắt đầu ngayBắt đầu miễn phí

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

Giờ bạn đã có mã để kiểm tra xem nút đích có nằm trong các hàng xóm hay không, bước tiếp theo, bạn sẽ mở rộng cùng hàm đó để viết mã cho trường hợp nút đích không nằm trong các hàng xóm.

Tất cả phần mã bạn cần viết nằm trong nhánh else; tức là khi node2 không có trong neighbors.

Bài tập này là một phần của khóa học

Nhập môn Phân tích Mạng bằng Python

Xem khóa học

Hướng dẫn bài tập

  • Sử dụng phương thức .add(), thêm nút hiện tại node vào tập visited_nodes để theo dõi những nút đã được thăm.
  • Thêm các hàng xóm của nút hiện tại node mà chưa được thăm vào queue. Để làm điều này, bạn cần dùng phương thức .extend() của queue cùng với một list comprehension. Phương thức .extend() sẽ nối tất cả phần tử trong một danh sách cho trước.
    • Cả biểu thức đầu rabiến lặp trong list comprehension đều là n. Iterable là bộ lặp của neighbors, và điều kiện là nếu n không nằm trong các nút đã thăm.

Bài tập tương tác thực hành trực tiếp

Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.

def path_exists(G, node1, node2):
    """
    This function checks whether a path exists between two nodes (node1, node2) in graph G.
    """
    visited_nodes = set()
    queue = [node1]

    for node in queue:
        neighbors = G.neighbors(node)
        if node2 in neighbors:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return True

        else:
            # Add current node to visited nodes
            ____

            # Add neighbors of current node that have not yet been visited
            queue.extend([____ for ____ in ____ if ____ not in ____])
Chỉnh sửa và Chạy Mã