Câu hỏi:
11/07/2024 149
Mở rộng bài tập trên cho đồ thị có hướng bất kì G = (V, E), được biểu diễn bởi ma trận kề A hoặc danh sách kề Adj. Viết hàm kiểm tra xem đồ thị G có chu trình hay không, nếu có thì hiển thị trên màn hình chu trình đó, bao gồm dãy các đỉnh tham gia vào chu trình.
Mở rộng bài tập trên cho đồ thị có hướng bất kì G = (V, E), được biểu diễn bởi ma trận kề A hoặc danh sách kề Adj. Viết hàm kiểm tra xem đồ thị G có chu trình hay không, nếu có thì hiển thị trên màn hình chu trình đó, bao gồm dãy các đỉnh tham gia vào chu trình.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Hướng dẫn phiên bản mẫu của hàm để kiểm tra xem một đồ thị có chu trình hay không, và nếu có, hiển thị chu trình đó:
def has_cycle_directed(graph):
def dfs(node, visited, stack):
visited[node] = True
stack.append(node)
for neighbor in graph[node]:
if neighbor in stack: # Nếu neighbor đã có trong stack, tức là tìm thấy chu trình
cycle_start = stack.index(neighbor)
return stack[cycle_start:]
if not visited[neighbor]: # Nếu neighbor chưa được thăm, tiếp tục duyệt DFS từ neighbor
result = dfs(neighbor, visited, stack)
if result: # Nếu tìm thấy chu trình từ neighbor, trả về chu trình
return result
stack.pop() # Loại bỏ node khỏi stack khi đã duyệt xong tất cả các neighbor của nó
return None
num_nodes = len(graph)
visited = [False] * num_nodes
for node in range(num_nodes):
cycle = dfs(node, visited, [])
if cycle: # Nếu tìm thấy chu trình từ đỉnh node, trả về chu trình
return cycle
return None
def get_cycle_nodes(cycle, graph):
cycle_nodes = []
for node in cycle:
cycle_nodes.append(node)
if node == cycle[-1]: # Nếu đỉnh hiện tại là đỉnh cuối cùng của chu trình
break
return cycle_nodes
def check_and_print_cycle(graph):
cycle = has_cycle_directed(graph)
if cycle:
cycle_nodes = get_cycle_nodes(cycle, graph)
print("Đồ thị có chu trình:", cycle_nodes)
else:
print("Đồ thị không có chu trình")
# Hàm kiểm tra và hiển thị chu trình trong đồ thị
graph_directed = {
0: [1],
1: [2],
2: [3],
3: [4],
4: [2] # Chu trình: 2 -> 3 -> 4 -> 2
}
check_and_print_cycle(graph_directed)
Trong mã này:
- Hàm has_cycle_directed sử dụng duyệt DFS để kiểm tra xem đồ thị có chu trình hay không. Nếu tìm thấy chu trình, nó trả về chu trình dưới dạng một danh sách các đỉnh.
- Hàm get_cycle_nodes giúp lấy ra danh sách các đỉnh tham gia vào chu trình từ chu trình được trả về bởi hàm has_cycle_directed.
- Hàm check_and_print_cycle kiểm tra và hiển thị chu trình trong đồ thị, nếu có
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu là vô hướng?
Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu là vô hướng?
Xem đáp án »
11/07/2024
143
Câu 2:
Trong lí thuyết đồ thị, chu trình được định nghĩa là một đường đi không tầm thường khép kín, tức là đường đi có số cạnh lớn hơn 1 và đỉnh xuất phát trùng với đỉnh kết thúc. Làm cách nào để kiểm tra một đồ thị cho trước có chu trình hay không?
Trong lí thuyết đồ thị, chu trình được định nghĩa là một đường đi không tầm thường khép kín, tức là đường đi có số cạnh lớn hơn 1 và đỉnh xuất phát trùng với đỉnh kết thúc. Làm cách nào để kiểm tra một đồ thị cho trước có chu trình hay không?
Xem đáp án »
11/07/2024
111
Câu 3:
Viết lại hàm kiểm tra chu trình DFS_acyclic(Adj,s) trong chương trình trên nhưng sử dụng phương án không đệ quy của thuật toán DFS.
Viết lại hàm kiểm tra chu trình DFS_acyclic(Adj,s) trong chương trình trên nhưng sử dụng phương án không đệ quy của thuật toán DFS.
Xem đáp án »
26/06/2024
71
Câu 4:
Sửa lại chương trình bổ sung thông báo nếu hệ thống chuyên đề không hợp lí thì thông báo dãy các chuyên đề có mâu thuẫn về kiến thức.
Sửa lại chương trình bổ sung thông báo nếu hệ thống chuyên đề không hợp lí thì thông báo dãy các chuyên đề có mâu thuẫn về kiến thức.
Xem đáp án »
26/06/2024
58
Bình luận
🔥 Đề thi HOT:
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
-
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 1
về câu hỏi!