Cho đơn đô thị G = V, E vô hướng hoặc có hướng. Cho trước hai đỉnh bất kì
Cho đơn đô thị G = (V, E) vô hướng hoặc có hướng. Cho trước hai đỉnh bất kì s và t. Viết chương trình kiểm tra xem có tồn tại đường đi từ s đến thay không. Nếu có thì chương trình cần chỉ ra dãy các đỉnh tương ứng trên đường đi từ s đến t, nói cách khác chương trình cần chỉ ra một dãy các đỉnh Vo, V1,..., Vk sao cho:
Giải Chuyên đề Tin 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng - Kết nối tri thức
Vận dụng 2 trang 79 Chuyên đề Tin học 12: Cho đơn đô thị G = (V, E) vô hướng hoặc có hướng. Cho trước hai đỉnh bất kì s và t. Viết chương trình kiểm tra xem có tồn tại đường đi từ s đến thay không. Nếu có thì chương trình cần chỉ ra dãy các đỉnh tương ứng trên đường đi từ s đến t, nói cách khác chương trình cần chỉ ra một dãy các đỉnh Vo, V1,..., Vk sao cho:
(Vj-1, Vj) là cạnh của đô thị với j = 1, 2, ..., k;
s = Vo, t = Vk
Lời giải:
Cài đặt Python cho chương trình kiểm tra xem có tồn tại đường đi từ đỉnh sss đến ttt, và nếu có, nó sẽ trả về dãy các đỉnh trên đường đi từ s đến t:
from collections import deque
def find_path(graph, start, end):
# Hàm duyệt đồ thị để tìm đường đi từ start đến end
def BFS(graph, start, end):
visited = set()
queue = deque([(start, [start])]) # Lưu trữ đường đi từ start đến đỉnh đang xét
while queue:
vertex, path = queue.popleft()
visited.add(vertex)
if vertex == end:
return path # Trả về đường đi nếu tìm thấy đỉnh kết thúc
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append((neighbor, path + [neighbor])) # Thêm đỉnh kề vào hàng đợi với đường đi mới
return None # Trả về None nếu không tìm thấy đường đi
# Kiểm tra xem có đường đi từ start đến end không
path = BFS(graph, start, end)
return path
# Ví dụ về đồ thị được biểu diễn bằng danh sách kề
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
start = 'A'
end = ‘F’
# Kiểm tra xem có tồn tại đường đi từ start đến end không
path = find_path(graph, start, end)
if path:
print("Đường đi từ", start, "đến", end, "là:", " -> ".join(path))
else:
print("Không tồn tại đường đi từ", start, "đến", end)
- Chú ý: Trong chương trình này, chúng ta sử dụng thuật toán BFS để duyệt đồ thị và tìm đường đi từ đỉnh sss đến ttt. Nếu đường đi được tìm thấy, chúng ta trả về dãy các đỉnh trên đường đi. Nếu không có đường đi, chúng ta trả về None.
Lời giải bài tập Chuyên đề Tin 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng hay, ngắn gọn khác: