Giải SGK Chuyên đề Tin học 12 Bài 15. Thực hành duyệt đồ thị theo chiều sâu

Để 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.

Để 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.

Phiên bản mẫu của hàm DFS_acyclic sử dụng phương pháp không đệ quy của thuật toán DFS để kiểm tra xem một đồ thị có chứa chu trình hay không:

def DFS_acyclic(Adj, s):

    stack = [(s, None)]  # Dùng stack để thực hiện DFS, cặp (đỉnh, đỉnh cha)

    visited = set()  # Dùng set để theo dõi các đỉnh đã thăm

    while stack:

        node, parent = stack.pop()  # Lấy đỉnh ra khỏi stack

        if node in visited:  # Nếu đỉnh đã được thăm trước đó

            return True  # Tìm thấy chu trình

        visited.add(node)  # Đánh dấu đỉnh đã thăm

        for neighbor in Adj[node]:  # Duyệt các đỉnh kề của đỉnh hiện tại

            if neighbor != parent:  # Tránh quay lại đỉnh cha

                stack.append((neighbor, node))  # Thêm đỉnh kề vào stack

    return False  # Không tìm thấy chu trình

# Sử dụng hàm kiểm tra chu trình không đệ quy

graph_undirected = {

    0: [1, 2],

    1: [0, 3],

    2: [0, 3],

    3: [1, 2]

}

if DFS_acyclic(graph_undirected, 0):

    print("Đồ thị vô hướng có chu trình")

else:

    print("Đồ thị vô hướng không có chu trình")

Trong hàm này:

- Chúng ta sử dụng một stack để thực hiện duyệt DFS thay vì đệ quy.

- Mỗi lần duyệt, chúng ta kiểm tra xem đỉnh hiện tại đã được thăm trước đó chưa. Nếu có, chúng ta tìm thấy chu trình.

- Nếu không, chúng ta đánh dấu đỉnh đó đã được thăm và duyệt qua tất cả các đỉnh kề của nó, tránh quay lại đỉnh.

Phiên bản mẫu gợi ý sửa đổi của chương trình để bổ sung thông báo nếu hệ thống chuyên đề không hợp lý và hiển thị dãy các chuyên đề có mâu thuẫn về kiến thức:

def DFS(graph, start, visited, stack):

    visited[start] = True

    for neighbor in graph[start]:

        if not visited[neighbor]:

            DFS(graph, neighbor, visited, stack)

    stack.append(start)

def topological_sort(graph):

    num_nodes = len(graph)

    visited = [False] * num_nodes

    stack = []

    for node in range(num_nodes):

        if not visited[node]:

            DFS(graph, node, visited, stack)

    return stack[::-1]

def is_valid_system(topological_order, prerequisites):

    knowledge = set()

    for course in topological_order:

        knowledge.add(course)

        if course in prerequisites:

            for prerequisite in prerequisites[course]:

                if prerequisite not in knowledge:

                    return False, [course, prerequisite]

    return True, None

def check_course_system(prerequisites):

    graph = {}

    for course, prereq in prerequisites.items():

        if course not in graph:

            graph[course] = []

        graph[course].extend(prereq)

    topological_order = topological_sort(graph)

    valid, conflicting_topics = is_valid_system(topological_order, prerequisites)

    if valid:

        print("Hệ thống chuyên đề hợp lý.")

    else:

        print("Hệ thống chuyên đề không hợp lý.")

        print("Dãy các chuyên đề có mâu thuẫn về kiến thức:", conflicting_topics)

# Dữ liệu chuyên đề và tiên điều kiện

prerequisites = {

    "A": ["B"],

    "B": ["C"],

    "C": ["D"],

    "D": ["A"]  # Mâu thuẫn về kiến thức với tiên điều kiện của D

}

# Kiểm tra hệ thống chuyên đề

check_course_system(prerequisites)

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ó