Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A

Giải Chuyên đề Tin 12 Bài 17: Thực hành duyệt đồ thị tổng hợp - Kết nối tri thức

Luyện tập 2 trang 82 Chuyên đề Tin học 12: Viết lại hàm BFS() trong chương trình trên nhưng sử dụng ma trận kề A thay thế cho danh sách kề Adj.

Lời giải:

Viết lại hàm BFS sử dụng ma trận kề A thay vì danh sách kề Adj. Dưới đây là cách triển khai:

from collections import deque

def BFS(graph, start):

    n = len(graph)

    visited = [False] * n

    visited[start] = True

    queue = deque([start])

    while queue:

        vertex = queue.popleft()

        print("Visit:", vertex)

        for neighbor in range(n):

            if graph[vertex][neighbor] == 1 and not visited[neighbor]:

                visited[neighbor] = True

                queue.append(neighbor)

# Ma trận kề mẫu

graph_matrix = [

    [0, 1, 1, 0, 0, 0],

    [1, 0, 0, 1, 1, 0],

    [1, 0, 0, 0, 0, 1],

    [0, 1, 0, 0, 0, 0],

    [0, 1, 0, 0, 0, 1],

    [0, 0, 1, 0, 1, 0]

]

# Thực hiện BFS từ đỉnh 0

BFS(graph_matrix, 0)

- Trong hàm BFS này, chúng ta duyệt qua các hàng của ma trận kề để xác định các đỉnh kề của mỗi đỉnh. Nếu có một đỉnh kề chưa được duyệt, chúng ta đánh dấu đỉnh đó đã được thăm và thêm nó vào hàng đợi để duyệt tiếp.

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

• Khởi động trang 80 Chuyên đề Tin học 12: Trong bài thực hành trước chúng ta đã được ôn tập và giải một số bài toán ....

• Luyện tập 1 trang 82 Chuyên đề Tin học 12: Sửa lại phần nhập dữ liệu hai học sinh: sẽ nhập trực tiếp tên hai học sinh, kiểm tra các tên ....

• Vận dụng 1 trang 82 Chuyên đề Tin học 12: Bổ sung thêm yêu cầu của nhiệm vụ trên như sau: Có hay không hai bạn học sinh ....

• Vận dụng 2 trang 82 Chuyên đề Tin học 12: Thiết lập hàm printpath(s,t) không đệ quy có tính năng tương tự hàm cùng tên ....

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 15: Thực hành 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

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

---