Cài đặt DFS cho đồ thị
Trong bài tập này, bạn sẽ cài đặt thuật toán depth first search để duyệt một đồ thị.
Nhắc lại các bước:
- Bắt đầu từ một đỉnh bất kỳ
- Thêm đỉnh đó vào danh sách các đỉnh đã thăm
- Với mỗi đỉnh kề của nút hiện tại
- Nếu đã được thăm -> bỏ qua
- Nếu chưa được thăm -> thực hiện DFS đệ quy
Để giúp bạn kiểm thử mã của mình, đồ thị sau đã được nạp bằng một dictionary.
graph = {
'0' : ['1','2'],
'1' : ['0', '2', '3'],
'2' : ['0', '1', '4'],
'3' : ['1', '4'],
'4' : ['2', '3']
}
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Hướng dẫn bài tập
- Kiểm tra nếu
current_vertexchưa được thăm. - Thêm
current_vertexvàovisited_vertices. - Gọi
dfs()đệ quy bằng cách truyền vào các giá trị phù hợp.
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
def dfs(visited_vertices, graph, current_vertex):
# Check if current_vertex hasn't been visited yet
if current_vertex not in ____:
print(current_vertex)
# Add current_vertex to visited_vertices
____.add(____)
for adjacent_vertex in graph[current_vertex]:
# Call recursively with the appropriate values
____(____, ____, ____)
dfs(set(), graph, '0')