Câu hỏi:
11/07/2024 206
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
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
Trả lời:
Giải bởi Vietjack
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.
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Thứ tự các đỉnh được duyệt khi thực hiện duyệt theo chiều sâu (DFS) và chiều rộng (BFS) bắt đầu từ đỉnh ‘a’:
Duyệt theo chiều sâu (DFS):
- Thứ tự có thể là: a, b, c, d, c, g, b, a, e, f.
Duyệt theo chiều rộng (BFS):
- Thứ tự có thể là: a, b, e, c, f, g, d.
Lời giải
Để kiểm tra xem đồ thị có chu trình hay không, ta có thể sử dụng thuật toán BFS để duyệt đồ thị và kiểm tra xem có đỉnh nào được duyệt lại không. Nếu có đỉnh nào đã được duyệt và nó là đỉnh kề của đỉnh hiện tại, thì đồ thị chứa chu trình.
Dưới đây là một cài đặt Python cho hàm Acycle(G):
from collections import deque
def Acycle(G):
# Hàm kiểm tra có chu trình hay không
def has_cycle(graph, start):
visited = set()
queue = deque([(start, None)]) # Lưu trữ cả cạnh đến đỉnh đang duyệt
while queue:
vertex, parent = queue.popleft()
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor != parent: # Loại bỏ trường hợp quay lại đỉnh cha
if neighbor in visited:
return True # Đồ thị có chu trình
else:
queue.append((neighbor, vertex)) # Thêm đỉnh kề vào hàng đợi
return False # Đồ thị không có chu trình
# Duyệt qua tất cả các đỉnh của đồ thị
for vertex in G:
if has_cycle(G, vertex):
return False # Nếu có chu trình, trả về False
return True # Nếu không có chu trình, trả về True
# 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']
}
# Kiểm tra đồ thị có chu trình hay không
print(Acycle(graph)) # False
- Chú ý: Trong hàm Acycle(G), ta duyệt qua tất cả các đỉnh của đồ thị và sử dụng hàm has_cycle(graph, start) để kiểm tra xem có chu trình bắt đầu từ đỉnh đó hay không. Nếu ta tìm thấy bất kỳ chu trình nào, ta trả về False. Nếu không có chu trình nào được tìm thấy, ta trả về True.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Mô hình và các giao thức mạng có đáp án
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 19 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 25 có đáp án
-
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 24 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Giới thiệu trí tuệ nhân tạo có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận