Câu hỏi:

11/07/2024 263

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 lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 12 KNTT Bài 15: Thực hành duyệt đồ thị theo chiều sâu có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

Để kiểm tra chu trình trong một đồ thị vô hướng, cách tiếp cận có thể khác so với đồ thị có hướng. Trong trường hợp đồ thị vô hướng, mỗi cạnh được coi là một liên kết giữa hai đỉnh, không có khái niệm đỉnh cha và đỉnh con.

Một cách để kiểm tra chu trình trong đồ thị vô hướng là sử dụng duyệt DFS nhưng cần phải theo dõi đỉnh trước đó mà không phải là đỉnh hiện tại (cha của đỉnh hiện tại) để tránh lặp lại qua cùng một cạnh. Nếu trong quá trình duyệt, gặp một đỉnh đã được thăm trước đó và không phải là đỉnh cha của đỉnh hiện tại, thì có thể kết luận rằng đồ thị chứa chu trình.

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:

Xem thêm »

Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

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

Lời giải

Để kiểm tra xem một đồ thị có chu trình hay không, chúng ta có thể sử dụng thuật toán DFS (Duyệt Đầu Tiên) hoặc BFS (Duyệt Theo Chiều Rộng). Dưới đây là cách kiểm tra bằng DFS:

- Bắt đầu từ một đỉnh bất kỳ trong đồ thị.

- Thực hiện duyệt DFS từ đỉnh này.

- Trong quá trình duyệt, nếu đỉnh nào đã được thăm trước đó và không phải là đỉnh cha của đỉnh hiện tại (trong trường hợp của cây), tức là tìm thấy một chu trình.

- Nếu tất cả các đỉnh đều đã được duyệt và không tìm thấy chu trình, đồ thị không chứa chu trình.

Câu 2

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.

Xem đáp án

Lời giải

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ó