Câu hỏi:
26/06/2024 25Viế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.
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
Chương trình Python mô phỏng thuật toán DFS theo cả hai cách đệ quy và không đệ quy:
* Đệ quy (Recursive):
def DFS_recursive(graph, vertex, visited=None):
if visited is None:
visited = set()
visited.add(vertex)
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
DFS_recursive(graph, neighbor, visited)
# Ví dụ sử dụng:
graph = {
0: [1, 2],
1: [3],
2: [4],
3: [],
4: [5],
5: [3],
6: [5],
7: [6]
}
DFS_recursive(graph, 0)
* Không đệ quy (Non-recursive):
def DFS_non_recursive(graph, start_vertex):
visited = set()
stack = [start_vertex]
while stack:
vertex = stack.pop()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
# Thêm vào ngăn xếp các đỉnh kề chưa được thăm
stack.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])
# Ví dụ sử dụng:
graph = {
0: [1, 2],
1: [3],
2: [4],
3: [],
4: [5],
5: [3],
6: [5],
7: [6]
}
DFS_non_recursive(graph, 0)
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).
Câu 2:
Nếu áp dụng thuật toán duyệt DFS cho đồ thị có hướng Hình 14.1b trong phần khởi động thì thứ tự các đỉnh được đánh dấu sẽ theo thứ tự nào?
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.
Câu 4:
Mô tả quá trình duyệt theo chiều sâu của đồ thị có hướng trong Hình 14.1b nếu xuất phát từ đỉnh 4.
Câu 5:
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).
Câu 6:
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ì.
Câu 7:
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?
về câu hỏi!