Thực hiện công việc duyệt theo chiều rộng của đồ thị Hình 16.1b, bắt đầu từ đỉnh 0. Các bước thực hiện sẽ duyệt các đỉnh theo trình tự sau:

- Mức 0: Bản thân đỉnh 0.

- Mức 1: Các đỉnh kề với đỉnh mức 0.

- Mức 2: Các đỉnh là kề với đỉnh mức 1. Đỉnh mức 2 là các đỉnh mà tồn tại đường đi từ đỉnh 0 đến đỉnh này theo 2 cạnh, qua đỉnh mức 1.

Quá trình cứ tiếp tục như vậy cho đến khi không thể duyệt thêm được nữa.

Trao đổi, thảo luận nhóm để nhận biết sự khác biệt giữa hai phương pháp duyệt đồ thị theo chiều sâu và chiều rộng khác nhau như thế nào.

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.

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