Đáp án và lời giải
Chuyên đề Tin 12 CTST Bài 3.4. Duyệt đồ thị theo chiều sâu
Câu 1
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Cho đồ thị G1 như ở Hình 1. Tìm đường đi ngắn nhất từ đỉnh H đến đỉnh D bằng thuật toán duyệt đồ thị theo chiều rộng như sau:
Câu 2
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Duyệt theo chiều sâu của đồ thị G2 ở Hình 2 (tương tự như Bảng 1) và bắt đầu từ đỉnh 2:
1. Duyệt đỉnh 2, thêm đỉnh 2 vào ngăn xếp
2
Đã duyệt
2
Stack
2. 1. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 3 của đỉnh 2 chưa duyệt. Duyệt đỉnh 3 và thêm đỉnh này vào ngăn xếp.
2
3
Đã duyệt
| 3 |
|---|
| 2 |
Stack
2. 2. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh 3 không có đỉnh kề chưa duyệt. Lấy đỉnh D ra khỏi ngăn xếp.
2
3
Đã duyệt
| 2 |
Stack
3. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 0 của đỉnh 2 chưa duyệt. Duyệt đỉnh 0 và thêm đỉnh này vào ngăn xếp.
2
3
4
0
Đã duyệt
| 0 |
|---|
| 4 |
| 2 |
Stack
4. Xem đỉnh 0 ở đỉnh ngăn xếp. Đỉnh kề 5 của đỉnh 0 chưa duyệt. Duyệt đỉnh 5 và thêm đỉnh này vào ngăn xếp.
2
3
4
0
5
Đã duyệt
| 5 |
|---|
| 0 |
| 4 |
| 2 |
Stack
5. Xem đỉnh 5 ở đỉnh ngăn xếp. Đỉnh kề 1 của đỉnh 5 chưa duyệt. Duyệt đỉnh 1 và thêm đỉnh này vào ngăn xếp.
2
3
4
0
1
Đã duyệt
| 1 |
|---|
| 0 |
| 4 |
| 3 |
| 2 |
Stack
6. Xem đỉnh 1 ở đỉnh ngăn xếp. Đỉnh 1 không có đỉnh chưa duyệt. Lấy đỉnh 1 ra khỏi ngăn xếp.
2
3
4
0
1
Đã duyệt
| 0 |
|---|
| 4 |
| 3 |
| 2 |
Stack
7. Xem đỉnh 0 ở đỉnh ngăn xếp. Đỉnh 0 không có đỉnh chưa duyệt. Lấy đỉnh 0 ra khỏi ngăn xếp.
2
3
4
0
1
Đã duyệt
| 4 |
|---|
| 3 |
| 2 |
Stack
7. Xem đỉnh 4 ở đỉnh ngăn xếp. Đỉnh 4 không có đỉnh chưa duyệt. Lấy đỉnh 4 ra khỏi ngăn xếp.
2
3
4
0
1
Đã duyệt
| 3 |
|---|
| 2 |
Stack
8. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh 3 không có đỉnh chưa duyệt. Lấy đỉnh 3 ra khỏi ngăn xếp.
2
3
4
0
1
Đã duyệt
2
Stack
9. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh 2 không có đỉnh chưa duyệt. Lấy đỉnh 2 ra khỏi ngăn xếp.
2
3
4
0
1
Đã duyệt
Stack
10. Ngăn xếp rỗng. Kết thúc. Thứ tự duyệt đồ thi theo chiều sâu là 2,3,4,0,1
2
3
4
0
1
Đã duyệt
Câu 3
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
1. Duyệt đỉnh 1, thêm đỉnh 1 vào ngăn xếp
1
Đã duyệt
1
Stack
2. Xem đỉnh 1 ở đỉnh ngăn xếp. Đỉnh kề 7 của đỉnh 1 chưa duyệt. Duyệt đỉnh 7 thêm đỉnh này vào ngăn xếp.
1
7
Đã duyệt
| 7 |
|---|
| 1 |
Stack
3. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 2 của đỉnh 7 chưa duyệt. Duyệt đỉnh 2 thêm đỉnh này vào ngăn xếp.
1
7
2
Đã duyệt
| 2 |
|---|
| 7 |
| 1 |
Stack
4. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 3 của đỉnh 2 chưa duyệt. Duyệt đỉnh 3 thêm đỉnh này vào ngăn xếp.
1
7
2
3
Đã duyệt
| 3 |
|---|
| 2 |
| 7 |
| 1 |
Stack
5. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh kề 4 của đỉnh 3 chưa duyệt. Duyệt đỉnh 4 thêm đỉnh này vào ngăn xếp.
1
7
2
3
4
Đã duyệt
| 4 |
|---|
| 3 |
| 2 |
| 7 |
| 1 |
Stack
6. Xem đỉnh 4 ở đỉnh ngăn xếp. Đỉnh kề 4 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 4 ra khỏi ngăn xếp ngăn xếp.
1
7
2
3
4
Đã duyệt
| 3 |
|---|
| 2 |
| 7 |
| 1 |
Stack
7. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh kề 5 của đỉnh kề 3 chưa duyệt. Duyệt đỉnh 5 vào ngăn xếp.
1
7
2
3
4
5
Đã duyệt
| 5 |
|---|
| 3 |
| 2 |
| 7 |
| 1 |
Stack
8. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 6 của đỉnh kề 7 chưa được duyệt. Duyệt đỉnh 6 ra vào ngăn xếp.
1
7
2
3
4
5
6
Đã duyệt
| 6 |
|---|
| 3 |
| 2 |
| 7 |
| 1 |
Stack
9. Xem đỉnh 6 ở đỉnh ngăn xếp. Đỉnh kề 6 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 6 ra khỏi ngăn xếp.
1
7
2
3
4
5
6
Đã duyệt
| 3 |
|---|
| 2 |
| 7 |
| 1 |
Stack
10. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 8 của đỉnh kề 7 chưa duyệt. Duyệt đỉnh 8 vào ngăn xếp.
1
7
2
3
4
5
6
8
Đã duyệt
| 8 |
|---|
| 3 |
| 2 |
| 7 |
| 1 |
Stack
11. Xem đỉnh 8 ở đỉnh ngăn xếp. Đỉnh kề 8 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 8 ra khỏi ngăn xếp.
1
7
2
3
4
5
6
8
Đã duyệt
| 3 |
|---|
| 2 |
| 7 |
| 1 |
Stack
12. Xem đỉnh 3 ở đỉnh ngăn xếp. Đỉnh kề 3 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 3 ra khỏi ngăn xếp.
1
7
2
3
4
5
6
8
Đã duyệt
| 2 |
|---|
| 7 |
| 1 |
Stack
13. Xem đỉnh 2 ở đỉnh ngăn xếp. Đỉnh kề 2 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 2 ra khỏi ngăn xếp.
1
7
2
3
4
5
6
8
Đã duyệt
| 7 |
|---|
| 1 |
Stack
14. Xem đỉnh 7 ở đỉnh ngăn xếp. Đỉnh kề 7 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 7 ra khỏi ngăn xếp.
1
7
2
3
4
5
6
8
Đã duyệt
1
Stack
15. Xem đỉnh 1 ở đỉnh ngăn xếp. Đỉnh kề 1 không có đỉnh kề nào chưa duyệt. Lấy đỉnh 7 ra khỏi ngăn xếp.
1
7
2
3
4
5
6
8
Đã duyệt
Stack
16. Ngăn xếp rỗng. Kết thúc. Thứ tự duyệt đồ thị theo chiều sâu là:
1
7
2
3
4
5
6
8
Đã duyệt
Câu 4
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
1. Duyệt đỉnh F, thêm đỉnh F vào ngăn xếp
F
Đã duyệt
F
Stack
2. Xem đỉnh F ở đỉnh ngăn xếp. Đỉnh kề B của đỉnh F chưa duyệt. Duyệt đỉnh B thêm đỉnh này vào ngăn xếp.
F
B
Đã duyệt
| B |
|---|
| F |
Stack
3. Xem đỉnh B ở đỉnh ngăn xếp. Đỉnh kề H của đỉnh B chưa duyệt. Duyệt đỉnh H thêm đỉnh này vào ngăn xếp.
F
B
H
Đã duyệt
| H |
|---|
| B |
| F |
Stack
3. Xem đỉnh H ở đỉnh ngăn xếp. Đỉnh kề J của đỉnh H chưa duyệt. Duyệt đỉnh J thêm đỉnh này vào ngăn xếp.
F
B
H
J
Đã duyệt
| J |
|---|
| H |
| B |
| F |
Stack
Câu 5
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
a) Biểu diễn đồ thị G4 thành danh sách kề.
def dft(graph, u): stack initStack()
#Khởi tạo stack rỗng
visited [vertices.index(u)] = True #Đánh dấu đỉnh u đã duyệt
print(u, end = " ")
push(stack, u)
#In đỉnh u
#Thêm đỉnh u vào stack
while not isEmptyStack(stack): #Lặp khi stack khác rỗng
p = top(stack)
found = False
for v in graph[p]:
#Xem đỉnh p ở đỉnh stack
#Chưa tìm thấy
#Lặp để lấy các đỉnh kề v của đỉnh p
if not visited[vertices.index(v)]: #Nếu đỉnh v chưa duyệt
found = True
break
if not found:
p = pop(stack)
else:
#Tìm thấy
#Không tìm thấy đỉnh v
#Lấy đỉnh p ra khỏi stack
#Tìm thấy đỉnh v chưa duyệt
visited[vertices.index(v)] = True #Đánh dấu đỉnh v đã duyệt
print(v, end = "")
push(stack, v)
#In đỉnh v
#Thêm đỉnh v vào stack
#Hàm duyệt graph dạng danh sách kế theo chiều sâu
def dfs(graph):
global visited
visited [False]
*
len(graph)
for u in graph:
if not visited [vertices.index(u)]:
dft(graph, u)
#Đánh dấu các đỉnh chưa duyệt
#Xét đỉnh u chưa duyệt
#Duyệt đô thị theo chiều sâu từ u
graph, vertices = createAdjListGraph('dothi.txt') #Tạo đô thị từ tập dfs(graph)
#In kết quả duyệt theo chiều sâu
b) Thực hiện chạy chương trình trên để duyệt đồ thị G4 được biểu diễn bằng danh sách kề.
c) Thực hiện chạy chương trình trên để duyệt đồ thị G4, được biểu diễn bằng danh sách kề, bắt đầu từ đỉnh 3.
Câu 6
Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý
Áp dụng thuật toán duyệt đồ thị theo chiều sâu. Thực hiện xây dựng thuật toán kiểm tra xem đồ thị G = (V, E) cho trước có liên thông hay không.
def dft(graph, u): stack initStack()
#Khởi tạo stack rỗng
visited [vertices.index(u)] = True #Đánh dấu đỉnh u đã duyệt
print(u, end = " ")
push(stack, u)
#In đỉnh u
#Thêm đỉnh u vào stack
while not isEmptyStack(stack): #Lặp khi stack khác rỗng
p = top(stack)
found = False
for v in graph[p]:
#Xem đỉnh p ở đỉnh stack
#Chưa tìm thấy
#Lặp để lấy các đỉnh kề v của đỉnh p
if not visited[vertices.index(v)]: #Nếu đỉnh v chưa duyệt
found = True
break
if not found:
p = pop(stack)
else:
#Tìm thấy
#Không tìm thấy đỉnh v
#Lấy đỉnh p ra khỏi stack
#Tìm thấy đỉnh v chưa duyệt
visited[vertices.index(v)] = True #Đánh dấu đỉnh v đã duyệt
print(v, end = "")
push(stack, v)
#In đỉnh v
#Thêm đỉnh v vào stack
#Hàm duyệt graph dạng danh sách kế theo chiều sâu
def dfs(graph):
global visited
visited [False]
*
len(graph)
for u in graph:
if not visited [vertices.index(u)]:
dft(graph, u)
#Đánh dấu các đỉnh chưa duyệt
#Xét đỉnh u chưa duyệt
#Duyệt đô thị theo chiều sâu từ u
graph, vertices = createAdjListGraph('dothi.txt') #Tạo đô thị từ tập dfs(graph)
#In kết quả duyệt theo chiều sâu