Các thuật toán DFS đã mô tả trong các phần trên đều thực hiện trên đồ thị

Giảm giá 50% sách VietJack đánh giá năng lực các trường trên Shopee Mall

Giải Chuyên đề Tin 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu - Kết nối tri thức

Vận dụng 2 trang 71 Chuyên đề Tin học 12: Các thuật toán DFS đã mô tả trong các phần trên đều thực hiện trên đồ thị được biểu diễn bằng danh sách kề Adj. Hãy viết lại hàm DFS() được thực hiện trên đồ thị được biểu diễn bằng ma trận kề A.

Quảng cáo

Lời giải:

Để viết lại hàm DFS thực hiện trên đồ thị được biểu diễn bằng ma trận kề A, chúng ta sẽ cần thay đổi cách truy cập các đỉnh kề từ việc duyệt danh sách kề sang việc duyệt ma trận kề.

Hàm DFS thực hiện trên ma trận kề ( bài mẫu tổng quát):

Giả sử ma trận kề A là một ma trận vuông kích thước n x n với n là số lượng đỉnh, trong đó A[i][j] = 1 nếu có cạnh nối từ đỉnh i đến đỉnh j, ngược lại A[i][j] = 0.

Dưới đây là cách viết lại hàm DFS:

python

Sao chép mã

def DFS(A, u, mark):

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

if not mark[u]:

mark[u] = True # Đánh dấu đỉnh u

print("Visit:", u) # In ra đỉnh đang được thăm

for v in range(n):

if A[u][v] == 1 and not mark[v]: # Kiểm tra nếu có cạnh và đỉnh v chưa được thăm

DFS(A, v, mark)

def main(A, start):

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

# Khởi tạo mảng đánh dấu cho tất cả các đỉnh

mark = [False] * n

# Gọi hàm DFS từ đỉnh bắt đầu

DFS(A, start, mark)

# Đồ 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 DFS từ đỉnh 'A' (tương ứng với chỉ số 0)

main(graph_matrix, 0)

Giải thích:

1. Hàm DFS:

Kiểm tra nếu đỉnh u chưa được đánh dấu.

Đánh dấu đỉnh u và in ra đỉnh đang được thăm.

Duyệt qua tất cả các đỉnh v từ 0 đến n-1 (vì n là số đỉnh).

Nếu A[u][v] == 1 (tức là có cạnh từ u đến v) và v chưa được thăm, thì gọi đệ quy DFS cho đỉnh v.

2. Hàm main:

Khởi tạo danh sách đánh dấu (mark) cho tất cả các đỉnh trong đồ thị, ban đầu tất cả đều là False.

Gọi hàm DFS từ đỉnh bắt đầu (start).

Quảng cáo

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

Quảng cáo

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:

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

Tài liệu cho giáo viên: Giáo án, powerpoint, đề thi giữa kì cuối kì, đánh giá năng lực, thi thử THPT, HSG, chuyên đề, bài tập cuối tuần..... độc quyền VietJack, giá hợp lí

Sách VietJack thi THPT quốc gia 2025 cho học sinh 2k7:

ĐỀ THI, GIÁO ÁN, GÓI THI ONLINE DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

Bộ giáo án, đề thi, bài giảng powerpoint, khóa học dành cho các thầy cô và học sinh lớp 12, đẩy đủ các bộ sách cánh diều, kết nối tri thức, chân trời sáng tạo tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official