Đườ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.
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
Hướng dẫn bài tập
- Tạo một hàm gọi là
path_exists()với 3 tham số -G,node1và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.queuenê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
node2có nằm trong tậpneighborshay không. Nếu có, trả vềTrue.
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.
# Define path_exists()
def ____:
"""
This function checks whether a path exists between two nodes (node1, node2) in graph G.
"""
visited_nodes = set()
# Initialize the queue of nodes to visit with the first node: queue
queue = ____
# Iterate over the nodes in the queue
for node in ____:
# Get neighbors of the node
neighbors = ____
# Check to see if the destination node is in the set of neighbors
if node2 in ____:
print('Path exists between nodes {0} and {1}'.format(node1, node2))
return ____
break