Chuyên đề Tin 12 CTST Bài 3.4. Duyệt đồ thị theo chiều sâu
39 người thi tuần này 4.6 142 lượt thi 6 câu hỏi
🔥 Đề thi HOT:
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 19 có đáp án
5.6 K lượt thi
15 câu hỏi
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
2.6 K lượt thi
15 câu hỏi
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 24 có đáp án
1.9 K lượt thi
15 câu hỏi
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 22 có đáp án
2.5 K lượt thi
15 câu hỏi
Trắc nghiệm tổng hợp Tin học năm 2023 có đáp án (Phần 4)
4.4 K lượt thi
217 câu hỏi
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 25 có đáp án
1.4 K lượt thi
15 câu hỏi
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 20 có đáp án
2.5 K lượt thi
15 câu hỏi
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 16 có đáp án
2.9 K lượt thi
15 câu hỏi
Nội dung liên quan:
Danh sách câu hỏi:
Lời giả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:
Lời giả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
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.
4.6
28 Đánh giá
50%
40%
0%
0%
0%