Chuyên đề Tin học 12 Bài 3.4 (Chân trời sáng tạo): Duyệt đồ thị theo chiều sâu

Giải Chuyên đề Tin học 12 Bài 3.4: Duyệt đồ thị theo chiều sâu

Khởi động trang 64 Chuyên đề Tin học 12: 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.

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:

1. Duyệt đồ thị theo chiều sâu

Câu hỏi trang 68 Chuyên đề Tin học 12: Em hãy minh hoạ 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.

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

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã 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

Đã duyệt

2. Thuật toán duyệt đồ thị theo chiều sâu

Câu hỏi trang 69 Chuyên đề Tin học 12: Hãy liệt kê thứ tự duyệt các đỉnh với thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh A của đồ thị G3 ở Hình 3.

Lời giải:

1. Duyệt đỉnh A, thêm đỉnh A vào ngăn xếp

Đã duyệt

Stack

2. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh kề H của đỉnh A chưa duyệt. Duyệt đỉnh H thêm đỉnh này vào ngăn xếp.

Đã duyệt

Stack

3. Xem đỉnh H ở đỉnh ngăn xếp. Đỉnh kề H của đỉnh J chưa duyệt. Duyệt đỉnh J thêm đỉnh này vào ngăn xếp.

Đã duyệt

Stack

4. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh J không có đỉnh kề chưa duyệt. Lấy đỉnh J ra khỏi ngăn xếp.

Đã duyệt

Stack

5. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh kề G của đỉnh A chưa duyệt. Duyệt đỉnh G, thêm đỉnh này vào ngăn xếp.

Đã duyệt

Stack

6. Xem đỉnh G ở đỉnh ngăn xếp. Đỉnh kề I của đỉnh G chưa duyệt. Duyệt đỉnh I, thêm đỉnh này vào ngăn xếp.

Đã duyệt

Stack

6. Xem đỉnh I ở đỉnh ngăn xếp. Đỉnh I không có đỉnh kề chưa duyệt. Lấy đỉnh I, ra khỏi ngăn xếp.

Đã duyệt

Stack

7. Xem đỉnh G ở đỉnh ngăn xếp. Đỉnh G có đỉnh kề F chưa duyệt. Thêm đỉnh F vào ngăn xếp.

Đã duyệt

Stack

8. Xem đỉnh F ở đỉnh ngăn xếp. Đỉnh F không có đỉnh kề chưa duyệt. Lấy đỉnh F ra khỏi ngăn xếp.

Đã duyệt

Stack

9. Xem đỉnh G ở đỉnh ngăn xếp. Đỉnh G không có đỉnh kề chưa duyệt. Lấy đỉnh G ra khỏi ngăn xếp.

Đã duyệt

Stack

10. Xem đỉnh H ở đỉnh ngăn xếp. Đỉnh H không có đỉnh kề chưa duyệt. Lấy đỉnh H ra khỏi ngăn xếp.

Đã duyệt

Stack

11. Xem đỉnh A ở đỉnh ngăn xếp. Đỉnh A không có đỉnh kề chưa duyệt. Lấy đỉnh A ra khỏi ngăn xếp.

Đã duyệt

Stack

12. Ngăn xếp rỗng. Kết thúc. Thứ tự duyệt đồ thị theo chiều sâu là:

Đã duyệt

Luyện tập 1 trang 70 Chuyên đề Tin học 12: Dùng thuật toán duyệt đồ thị theo chiều sâu xuất phát từ đỉnh 1. Hãy cho biết thứ tự duyệt các đỉnh của đồ thị ở Hình 4.

Lời giải:

1. Duyệt đỉnh 1, thêm đỉnh 1 vào ngăn xếp

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã 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à:

Đã duyệt

Luyện tập 2 trang 70 Chuyên đề Tin học 12: Cho đồ thị G5 (Hình 5). Chỉ ra đường đi từ đỉnh F đến đỉnh J bằng thuật toán duyệt đồ thị theo chiều sâu trong đồ thị G5.

Lời giải:

1. Duyệt đỉnh F, thêm đỉnh F vào ngăn xếp

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

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.

Đã duyệt

Stack

Thực hành trang 70 Chuyên đề Tin học 12: Nhiệm vu: Duyệt đồ thị theo chiều sâu

Yêu cầu: Chương trình sau được viết bằng Phython duyệt đồ thị theo chiều sâu, với đồ thị Graph được biểu diễn bằng danh sách kề.

Lời giả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.

Vận dụng trang 71 Chuyên đề Tin học 12: Nhiệm vụ. Kiểm tra đô thị liên thông

Một đồ thị được gọi là liên thông nếu tồn tại ít nhất một đường đi giữa hai đỉnh bất kì của nó. Chẳng hạn, đồ thị ở Hình 6a là liên thông còn đô thị ở Hình 6b là không liên thông (không có đường đi từ đỉnh 0 tới đỉnh 3).

Yêu cầu: Á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.

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

Xem thêm các bài giải Chuyên đề Tin học 12 sách Chân trời sáng tạo hay, chi tiết khác:

Bài 2.4: Thực hành cây tìm kiếm nhị phân

Bài 3.1: Các khái niệm cơ bản của đồ thị

Bài 3.2: Biểu diễn đồ thị

Bài 3.3: Duyệt đồ thị theo chiều rộng

Bài 3.5: Thực hành kĩ thuật duyệt đồ thị