Đườ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
Hướng dẫn bài tập
- Sử dụng phương thức
.add(), thêm nút hiện tạinodevào tậpvisited_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
nodemà chưa được thăm vàoqueue. Để làm điều này, bạn cần dùng phương thức.extend()củaqueuecù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 ra và biến lặp trong list comprehension đều là
n. Iterable là bộ lặp củaneighbors, và điều kiện là nếunkhông nằm trong các nút đã thăm.
- Cả biểu thức đầu ra và biến lặp trong list comprehension đều là
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 ____])