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

Giải Chuyên đề Tin 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu - Kết nối tri thức

Vận dụng 2 trang 74 Chuyên đề Tin học 12: 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.

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ó

Lời giải bài tập Chuyên đề Tin 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu hay, ngắn gọn khác:

• Khởi động trang 72 Chuyên đề Tin học 12: Trong lí thuyết đồ thị, chu trình được định nghĩa là một đường đi không tầm thường ....

• Luyện tập 1 trang 74 Chuyên đề Tin học 12: Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu ....

• Luyện tập 2 trang 74 Chuyên đề Tin học 12: Viết lại hàm kiểm tra chu trình DFS_acyclic(Adj,s) trong chương trình ....

• Vận dụng 1 trang 74 Chuyên đề Tin học 12: 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í ....

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:

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

• Chuyên đề Tin học 12 Bài 17: Thực hành duyệt đồ thị tổng hợp

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

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---