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

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

Đây là bài cuối cùng trong bộ ba! Giờ bạn sẽ hoàn thiện bài toán bằng cách viết mã trả về False nếu không có đường đi giữa hai nút.

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

  • Kiểm tra xem hàng đợi đã trống chưa. Bạn có thể làm điều này bằng cách xem phần tử cuối của hàng đợi với [-1].
  • Đặt câu lệnh return phù hợp để cho biết có hay không có đường đi giữa hai nút này.

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 = list(G.neighbors(node))
        if node2 in neighbors:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return True
            break

        else:
            visited_nodes.add(node)
            queue.extend([n for n in neighbors if n not in visited_nodes])

        # Check to see if the final element of the queue has been reached
        if node == ____:
            print('Path does not exist between nodes {0} and {1}'.format(node1, node2))

            # Place the appropriate return statement
            return ____
Chỉnh sửa và Chạy Mã