Cho đơn đô thị G = V, E vô hướng hoặc có hướng. Cho trước hai đỉnh bất kì

Giảm giá 50% sách VietJack đánh giá năng lực các trường trên Shopee Mall

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

Quảng cáo

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.

Quảng cáo

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:

Quảng cáo

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Tài liệu cho giáo viên: Giáo án, powerpoint, đề thi giữa kì cuối kì, đánh giá năng lực, thi thử THPT, HSG, chuyên đề, bài tập cuối tuần..... độc quyền VietJack, giá hợp lí

Sách VietJack thi THPT quốc gia 2025 cho học sinh 2k7:

ĐỀ THI, GIÁO ÁN, GÓI THI ONLINE DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

Bộ giáo án, đề thi, bài giảng powerpoint, khóa học dành cho các thầy cô và học sinh lớp 12, đẩy đủ các bộ sách cánh diều, kết nối tri thức, chân trời sáng tạo tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official