Câu hỏi:
11/07/2024 101
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.
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.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Để 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).
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS – Depth First Search).
Tìm hiểu ý tưởng của thuật toán duyệt đồ thị theo chiều sâu (DFS – Depth First Search).
Xem đáp án »
11/07/2024
263
Câu 2:
Viết chương trình in ra thứ tự các đỉnh đã được duyệt bằng thuật toán DFS theo cả hai cách đệ quy và không đệ quy, áp dụng cho đồ thị có hướng Hình 14.1b trong phần Khởi động.
Viết chương trình in ra thứ tự các đỉnh đã được duyệt bằng thuật toán DFS theo cả hai cách đệ quy và không đệ quy, áp dụng cho đồ thị có hướng Hình 14.1b trong phần Khởi động.
Xem đáp án »
11/07/2024
199
Câu 3:
Tìm hiểu một cách cài đặt khác của thuật toán duyệt theo chiều sâu DFS không sử dụng kĩ thuật đệ quy.
Tìm hiểu một cách cài đặt khác của thuật toán duyệt theo chiều sâu DFS không sử dụng kĩ thuật đệ quy.
Xem đáp án »
11/07/2024
196
Câu 4:
Sửa chương trình của thuật toán DFS không đệ quy sao cho chương trình trong khi duyệt sẽ in ra các bước với thông tin sau:
– Thông tin ngăn xếp (hiện thời).
– Phần tử được lấy ra từ ngăn xếp.
– Phần tử được đánh dấu để chuẩn bị cho bước sau (mark).
Sửa chương trình của thuật toán DFS không đệ quy sao cho chương trình trong khi duyệt sẽ in ra các bước với thông tin sau:
– Thông tin ngăn xếp (hiện thời).
– Phần tử được lấy ra từ ngăn xếp.
– Phần tử được đánh dấu để chuẩn bị cho bước sau (mark).
Xem đáp án »
11/07/2024
167
Câu 5:
Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau:
– Kiểu dữ liệu mảng (một hoặc hai chiều).
– Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân).
Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó.
Chúng ta đã biết bài toán và thuật toán duyệt (tìm kiếm) dữ liệu trên các cấu trúc dữ liệu khác nhau:
– Kiểu dữ liệu mảng (một hoặc hai chiều).
– Kiểu dữ liệu cây (cây nhị phân và cây tìm kiếm nhị phân).
Vậy với dữ liệu của đồ thị, việc duyệt các đỉnh của đồ thị sẽ được thực hiện như thế nào? Quan sát hai đồ thị ở Hình 14.1 và thảo luận với bạn cách thực hiện duyệt trên các đỉnh của đồ thị đó.
Xem đáp án »
26/06/2024
114
Câu 6:
Thứ tự các đỉnh trong danh sách kề có ảnh hưởng đến thứ tự các đỉnh được duyệt của thuật toán DFS không?
Thứ tự các đỉnh trong danh sách kề có ảnh hưởng đến thứ tự các đỉnh được duyệt của thuật toán DFS không?
Xem đáp án »
11/07/2024
114
Câu 7:
Quan sát, thảo luận và tìm hiểu thuật toán duyệt theo chiều sâu trên đồ thị bất kì.
Quan sát, thảo luận và tìm hiểu thuật toán duyệt theo chiều sâu trên đồ thị bất kì.
Xem đáp án »
11/07/2024
105
Bình luận
🔥 Đề thi HOT:
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
-
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 1
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
về câu hỏi!