Câu hỏi:
04/10/2024 151
Cho đồ thị G1 như ở Hình 1. Hãy 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.
Cho đồ thị G1 như ở Hình 1. Hãy 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.
Quảng cáo
Trả lời:
Giải bởi Vietjack
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:
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
- Sổ tay dẫn chứng nghị luận xã hội năm 2025 (chương trình mới) ( 18.000₫ )
- Sổ tay Hóa học 12 (chương trình mới) ( 18.000₫ )
- Sổ tay lớp 12 các môn Toán, Lí, Hóa, Văn, Sử, Địa, KTPL (chương trình mới) ( 36.000₫ )
- Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia Hà Nội, TP Hồ Chí Minh (2 cuốn) ( 150.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giả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
Lời giả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
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Mô hình và các giao thức mạng có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Giới thiệu trí tuệ nhân tạo có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 19 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 25 có đáp án
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 2
-
Trắc nghiệm tổng hợp Tin học năm 2023 có đáp án (Phần 1)
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 26 có đáp án