Tìm đường di bằng thuật toán duyệt đồ thị theo chiều sâu trang 76 Chuyên đề Tin học 12

Giải Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị - Chân trời sáng tạo

Nhiệm vụ 2 trang 76 Chuyên đề Tin học 12: Tìm đường di bằng thuật toán duyệt đồ thị theo chiều sâu

Yêu cầu; Cho bản đó (Hình 2) gồm các thành phố M, N, P, Q, R được biểu diễn bởi đồ thị. Dựa vào thuật toán duyệt đồ thị theo chiều sâu được biểu diễn bằng ma trận kể, viết chương trình in ra màn hình đường đi từ thành phố M đến thành phố R.

Dữ liệu vào: Tệp dothitxt chứa dữ liệu của đô thị. Hàng đầu tiên là danh sách các đỉnh của đô thị. Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn. Dữ liệu ra: Các dỉnh của đường di từ dỉnh M đến dỉnh R

Lời giải:

def dfs(G, u):

Xử lí đỉnh u

Đánh dấu duyệt đỉnh u

for đỉnh v là đỉnh kế của đỉnh u:

if đỉnh v chưa được đánh dấu duyệt: dfs(G, v)

Thuật toán duyệt đô thị theo chiều sâu bắt đầu từ đỉnh u:

def dft(G, u):

Khởi tạo ngăn xếp stack rỗng

Xử lí đỉnh u

Đánh dấu duyệt đỉnh u

Thêm đỉnh u vào ngăn xếp stack while ngăn xếp stack khác rỗng:

Xem đỉnh p ở đầu ngăn xếp stack

#Xét các đỉnh kề v chưa được duyệt của đình p found False

for đỉnh v thuộc tập đỉnh kề của đỉnh p: if đỉnh v chưa duyệt:

found=True break

if not found:

Lấy đỉnh p ra khỏi ngăn xếp stack

else:

Xử lí đỉnh v

Đánh dấu duyệt đỉnh v

Thêm đỉnh v vào ngăn xếp stack

Thuật toán duyệt theo chiều sâu các đỉnh của đô thị G được minh hoạ như sau:

def dfs(G):

for đỉnh u thuộc G.

Đánh dấu đỉnh  u chưa duyệt.

For đỉnh u thuộc G.

If đỉnh u chưa duyệt

Dft(G,u)

Lời giải bài tập Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị hay, chi tiết khác:

• Khởi động trang 72 Chuyên đề Tin học 12: Nêu một ứng dụng của một trong hai thuật toán duyệt đồ thị đã học ....

• Nhiệm vụ 1 trang 72 Chuyên đề Tin học 12: Nhiệm vụ 1. Chương trình tìm đường đi bằng thuật toán duyệt đồ thị theo chiều rộng ....

• Nhiệm vụ 2 trang 74 Chuyên đề Tin học 12: Chương trình tìm đường đi bằng thuật toán duyệt đô thị theo chiều sâu ....

• Nhiệm vụ 1 trang 75 Chuyên đề Tin học 12: Tìm đường đi bằng thuật toán duyệt đô thị theo chiều rộng ....

• Vận dụng trang 76 Chuyên đề Tin học 12: Nhiệm vụ. Đếm số thành phần liên thông của đồ thị ....

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

• Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin 12 Bài 3.1: Các khái niệm cơ bản của đồ thị

• Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị

• Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng

• Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---