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

Câu 1

Trả lời câu hỏi Khởi động trang 75 Chuyên đề Tin học 12 Kết nối tri thức

Chúng ta đã làm quen với thuật toán duyệt đồ thị theo chiều sâu, quá trình duyệt đi "sâu" nhất có thể theo các cạnh của đồ thị. Ngoài ra còn có cách duyệt đồ thị theo chiều rộng, được hình dung như khi đổ nước xuống một sàn nhà phẳng, nước sẽ lan toả ra xung quanh theo các hình tròn đồng tâm. Cách duyệt theo chiều rộng có thể được mô phỏng như Hình 16.12.

Giả sử ta bắt đầu duyệt từ đỉnh 0 của đồ thị Hình 16.1b theo chiều rộng. Theo em, chúng ta sẽ duyệt các đỉnh theo nguyên tắc nào và duyệt theo thứ tự nào?

Lời giải chi tiết:

Thuật toán duyệt theo chiều rộng (BFS) bắt đầu từ một đỉnh và duyệt qua tất cả các đỉnh kề với nó trước, sau đó mới chuyển sang các đỉnh kề của các đỉnh đã duyệt. Khi duyệt từ đỉnh 0 của đồ thị Hình 16.1b, chúng ta sẽ tuân theo nguyên tắc sau:

- Nguyên tắc duyệt:

+ Duyệt tất cả các đỉnh kề với đỉnh hiện tại trước khi chuyển sang đỉnh kề tiếp theo.

+ Sử dụng hàng đợi (queue) để lưu trữ thứ tự duyệt.

- Thứ tự duyệt có thể là:

+ Bắt đầu từ đỉnh 0, thăm tất cả các đỉnh kề với đỉnh 0.

+ Sau đó, duyệt qua các đỉnh kề với các đỉnh đã thăm theo thứ tự từ hàng đợi.

+ Tiếp tục quá trình này cho đến khi tất cả các đỉnh đều được thăm.

Câu 2

Trả lời câu hỏi Hoạt động 1 trang 75 Chuyên đề Tin học 12 Kết nối tri thức

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.

Lời giải chi tiết:

Để thực hiện duyệt theo chiều rộng (BFS) từ đỉnh 0 của đồ thị, chúng ta sẽ tuân theo các bước sau:

- Mức 0: Bắt đầu từ đỉnh 0.

- Mức 1: Duyệt tất cả các đỉnh kề với đỉnh 0.

- Mức 2: Duyệt tất cả các đỉnh kề với các đỉnh ở Mức 1 và không phải là đỉnh 0.

- Các Mức tiếp theo: Tiếp tục duyệt các đỉnh kề với đỉnh ở mức trước đó, không lặp lại các đỉnh đã duyệt.

Quá trình này tiếp tục cho đến khi tất cả các đỉnh có thể tiếp cận từ đỉnh 0 đều được duyệt.

Sự khác biệt chính giữa hai phương pháp duyệt đồ thị theo chiều sâu (DFS) và chiều rộng (BFS) là:

- DFS: Duyệt sâu vào từng nhánh của đồ thị trước khi quay lại (backtrack).

- BFS: Duyệt đồ thị theo từng mức độ rộng, từ gần đến xa so với điểm bắt đầu.

Câu 3

Trả lời câu hỏi 1 trang 76 Chuyên đề Tin học 12 Kết nối tri thức

Mệnh đề sau đúng hay sai?

Giả sử gọi BFS(Adj,s) là chương trình duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh s. Khi đó với mọi đỉnh v thuộc V, hàm BFS(Adj,s) sẽ duyệt qua đỉnh v khi và chỉ khi tồn tại đường đi từ s đến v.

Lời giải chi tiết:

Mệnh đề sau là đúng.

- Lý do:

Mệnh đề này có thể được chứng minh tương tự như cách chứng minh tính chất của DFS đối với đường đi trong đồ thị. Cụ thể:

- Chứng minh:

Chúng ta cần chứng minh hai điều sau:

1. Nếu tồn tại đường đi từ đỉnh sss đến đỉnh v, thì quá trình duyệt BFS từ đỉnh sss sẽ duyệt qua đỉnh v.

2. Nếu quá trình duyệt BFS từ đỉnh sss duyệt qua đỉnh v, thì tồn tại đường đi từ đỉnh sss đến đỉnh v.

- Chứng minh điều 1:

Nếu tồn tại đường đi từ đỉnh s đến đỉnh v:

- Giả sử tồn tại một đường đi từ đỉnh sss đến đỉnhv. Điều này có nghĩa là có một dãy các đỉnh s=v0,v1,v2,…,vk sao cho (vi,vi+1) ∈ E

- Khi thực hiện BFS từ đỉnh sss, BFS sẽ thăm tất cả các đỉnh mà nó có thể truy cập được từ sss. BFS duyệt các đỉnh theo từng mức (level) một cách rộng nhất có thể trước khi chuyển sang mức tiếp theo.

- Điều này bao gồm các đỉnh v1,v2,…,vk vì chúng liên tiếp nhau trong đường đi từ s đến v.

- Do đó, nếu tồn tại đường đi từ đỉnh s đến đỉnh v, BFS sẽ chắc chắn thăm đỉnh v trong quá trình duyệt.

- Chứng minh điều 2:

Nếu quá trình duyệt BFS từ đỉnh sss duyệt qua đỉnh v:

- Giả sử quá trình duyệt BFS từ đỉnh sss duyệt qua đỉnh v. Điều này có nghĩa là BFS đã bắt đầu từ đỉnh sss và theo các cạnh của đồ thị, nó đã đến đỉnh v.

- BFS duyệt đồ thị bằng cách đi theo các cạnh của đồ thị, nên mỗi bước từ đỉnh hiện tại đến đỉnh tiếp theo trong quá trình duyệt BFS đều là di chuyển qua các cạnh của đồ thị.

- Nếu BFS đã thăm đỉnh v từ đỉnh s, điều đó có nghĩa là có một dãy các đỉnh bắt đầu từ sss và kết thúc tại v sao cho mỗi đỉnh trong dãy này đều có cạnh nối với đỉnh tiếp theo trong dãy.

- Do đó, tồn tại một đường đi từ đỉnh s đến đỉnh v.

Câu 4

Trả lời câu hỏi 2 trang 76 Chuyên đề Tin học 12 Kết nối tri thức

Trả lời các câu hỏi dựa trên đồ thị Hình 16.2.

a) Các đỉnh kề với a là đỉnh nào?

b) Khoảng cách từ đỉnh a đến e là bao nhiêu?

c) Nếu thực hiện duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh a thì thứ tự các đỉnh được duyệt có thể như thế nào?

Lời giải chi tiết:

a) Các đỉnh kề với a:

Đỉnh ‘b’, ‘c’ là các đỉnh kề với đỉnh ‘a’.

b) Khoảng cách từ a đến e:

Khoảng cách ngắn nhất từ đỉnh ‘a’ đến đỉnh ‘e’ là ba cạnh, thông qua đỉnh ‘c’ và ‘h’.

c) Thứ tự duyệt đồ thị theo chiều rộng từ a:

Một thứ tự có thể là: a, b, c, d, f, g, e, h.

Câu 5

Trả lời câu hỏi Hoạt động 2 trang 77 Chuyên đề Tin học 12 Kết nối tri thức

Tìm hiểu, thảo luận về cách cài đặt thuật toán theo chiều rộng.

Lời giải chi tiết:

Thuật toán duyệt theo chiều rộng (Breadth-First Search, BFS) là một thuật toán duyệt hoặc tìm kiếm trên cây hoặc đồ thị. BFS bắt đầu từ một đỉnh gốc và khám phá các đỉnh lân cận trước khi di chuyển đến các đỉnh xa hơn. Đây là một phương pháp duyệt theo tầng (level-order traversal).

Cài đặt thuật toán BFS

Để cài đặt BFS, chúng ta cần sử dụng một hàng đợi (queue) để theo dõi các đỉnh sẽ được thăm tiếp theo. Hàng đợi đảm bảo rằng các đỉnh được thăm theo thứ tự mà chúng được khám phá.

Dưới đây là các bước cơ bản để cài đặt BFS:

- Khởi tạo hàng đợi: Đẩy đỉnh bắt đầu vào hàng đợi và đánh dấu nó đã được thăm.

- Duyệt đỉnh: Lặp lại quá trình sau cho đến khi hàng đợi rỗng:

+ Lấy đỉnh ở đầu hàng đợi ra.

+ Duyệt tất cả các đỉnh kề của đỉnh này. Nếu một đỉnh kề chưa được thăm, đánh dấu nó đã được thăm và đẩy nó vào hàng đợi.

Câu 6

Trả lời câu hỏi 1 trang 79 Chuyên đề Tin học 12 Kết nối tri thức

Thứ tự các đỉnh có trong danh sách đỉnh kề Adj có ảnh hưởng đến thứ tự các đỉnh được đánh dấu trong thuật toán duyệt theo chiều rộng hay không?

Lời giải chi tiết:

Thứ tự các đỉnh có trong danh sách đỉnh kề (Adjacency List) có ảnh hưởng đến thứ tự các đỉnh được đánh dấu trong thuật toán duyệt theo chiều rộng (BFS).

Ảnh hưởng của thứ tự đỉnh trong danh sách đỉnh kề:

1. Thứ tự duyệt các đỉnh gần gốc trước: Nếu đỉnh gốc nằm ở đầu danh sách đỉnh kề, các đỉnh gần gốc sẽ được duyệt trước. Điều này có thể dẫn đến việc duyệt đồ thị theo một hướng cụ thể và có thể tạo ra kết quả khác nhau nếu thứ tự này được thay đổi.

2. Thứ tự duyệt các đỉnh xa gốc sau: Các đỉnh ở phía sau trong danh sách sẽ được duyệt sau. Do đó, các đỉnh xa gốc sẽ được duyệt sau khi đã duyệt qua các đỉnh gần gốc.

Câu 7

Trả lời câu hỏi 2 trang 79 Chuyên đề Tin học 12 Kết nối tri thức

Cho đồ thị Hình 16.4. Nếu thực hiện duyệt theo chiều sâu và chiều rộng bắt đầu từ đỉnh a thì thứ tự các đỉnh được duyệt sẽ như thế nào?

Lời giải chi tiết:

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.

Luyện tập Câu 1

Trả lời câu hỏi Luyện tập 1 trang 79 Chuyên đề Tin học 12 Kết nối tri thức

Viết lại hàm BFS() in ra các đỉnh đã duyệt. Áp dụng vào đồ thị trong bài để kiểm tra thứ tự các đỉnh đã duyệt có đúng như phần mô phỏng thủ công các hoạt động trên không.

Lời giải chi tiết:

Gợi ý viết tổng quát của hàm BFS sử dụng ma trận kề của đồ thị:

from collections import deque

def BFS(matrix, start):

    n = len(matrix)  # Số lượng đỉnh trong đồ thị

    visited = set()  # Sử dụng một set để lưu trữ các đỉnh đã được duyệt

    queue = deque([start])  # Khởi tạo hàng đợi và thêm đỉnh bắt đầu vào đó

    while queue:

        vertex = queue.popleft()  # Lấy đỉnh ở đầu hàng đợi ra

        if vertex not in visited:

            print("Visit:", vertex)  # In ra đỉnh đã duyệt

            visited.add(vertex)  # Đánh dấu đỉnh đã duyệt

            for neighbor in range(n):  # Duyệt qua tất cả các đỉnh

                if matrix[vertex][neighbor] == 1 and neighbor not in visited:

                    queue.append(neighbor)  # Thêm các đỉnh kề chưa được duyệt vào hàng đợi

# Đồ thị mẫu dưới dạng ma trận kề

graph_matrix = [

    [0, 1, 1, 0, 0, 0],  # A

    [1, 0, 0, 1, 1, 0],  # B

    [1, 0, 0, 0, 0, 1],  # C

    [0, 1, 0, 0, 0, 0],  # D

    [0, 1, 0, 0, 0, 1],  # E

    [0, 0, 1, 0, 1, 0]   # F

]

# Thực hiện BFS từ đỉnh 0 (tương ứng với đỉnh 'A')

BFS(graph_matrix, 0)

- Chú ý: Trong hàm BFS này, ta sử dụng ma trận kề matrix để xác định các đỉnh kề của mỗi đỉnh. Nếu một đỉnh kề chưa được duyệt, ta thêm nó vào hàng đợi để duyệt tiếp. Quá trình này được lặp lại cho tất cả các đỉnh kề của mỗi đỉnh được duyệt.

Luyện tập Câu 2

Trả lời câu hỏi Luyện tập 2 trang 79 Chuyên đề Tin học 12 Kết nối tri thức

Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A của đồ thị.

Lời giải chi tiết:

Viết lại hàm BFS() duyệt theo chiều rộng nhưng sử dụng dữ liệu là ma trận kề A của đồ thị.

Vận dụng Câu 1

Trả lời câu hỏi Vận dụng 1 trang 79 Chuyên đề Tin học 12 Kết nối tri thức

Cho đơn đồ thị vô hướng G = (V, E). Sử dụng thuật toán duyệt theo chiều rộng BFS, viết chương trình kiểm tra xem G có chu trình hay không. Chu trình (cycle) ở đây được hiểu là một đường đi khép kín, đỉnh xuất phát trùng với đỉnh kết thúc. Cần thiết lập hàm dạng Acycle(G), hàm trả lại True nếu G không có chu trình, ngược lại hàm trả lại False.

Lời giải chi tiết:

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

Vận dụng Câu 2

Trả lời câu hỏi Vận dụng 2 trang 79 Chuyên đề Tin học 12 Kết nối tri thức

Cho đơn đô thị G = (V, E) vô hướng hoặc có hướng. Cho trước hai đỉnh bất kì s và t. Viết chương trình kiểm tra xem có tồn tại đường đi từ s đến thay không. Nếu có thì chương trình cần chỉ ra dãy các đỉnh tương ứng trên đường đi từ s đến t, nói cách khác chương trình cần chỉ ra một dãy các đỉnh Vo, V1,..., Vk sao cho:

(Vj-1, Vj) là cạnh của đô thị với j = 1, 2, ..., k;

s = Vo, t = Vk

Lời giải chi tiết:

Cài đặt Python cho chương trình kiểm tra xem có tồn tại đường đi từ đỉnh sss đến ttt, và nếu có, nó sẽ trả về dãy các đỉnh trên đường đi từ s đến t:

from collections import deque

def find_path(graph, start, end):

    # Hàm duyệt đồ thị để tìm đường đi từ start đến end

    def BFS(graph, start, end):

        visited = set()

        queue = deque([(start, [start])])  # Lưu trữ đường đi từ start đến đỉnh đang xét

        while queue:

            vertex, path = queue.popleft()

            visited.add(vertex)

            if vertex == end:

                return path  # Trả về đường đi nếu tìm thấy đỉnh kết thúc

            for neighbor in graph[vertex]:

                if neighbor not in visited:

                    queue.append((neighbor, path + [neighbor]))  # Thêm đỉnh kề vào hàng đợi với đường đi mới

        return None  # Trả về None nếu không tìm thấy đường đi

    # Kiểm tra xem có đường đi từ start đến end không

    path = BFS(graph, start, end)

    return path

# 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']

}

start = 'A'

end = ‘F’

# Kiểm tra xem có tồn tại đường đi từ start đến end không

path = find_path(graph, start, end)

if path:

    print("Đường đi từ", start, "đến", end, "là:", " -> ".join(path))

else:

    print("Không tồn tại đường đi từ", start, "đến", end)

- Chú ý: Trong chương trình này, chúng ta sử dụng thuật toán BFS để duyệt đồ thị và tìm đường đi từ đỉnh sss đến ttt. Nếu đường đi được tìm thấy, chúng ta trả về dãy các đỉnh trên đường đi. Nếu không có đường đi, chúng ta trả về None.