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

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ị

Một đô thị G được gọi là không liên thông nếu tổn tại đỉnh u và đỉnh v thuộc G mà không có đường đi giữa hai đỉnh này. Khi đó, đỉnh u và đỉnh v thuộc hai thành phần liên thông khác nhau. Nếu tồn tại đường đi giữa đỉnh u và đỉnh v thì hai đỉnh này phải thuộc cùng một thành phần liên thông. Như vậy, đô thị G không liên thông sẽ có ít nhất hai thành phần liên thông. Yêu cầu: Cho đồ thị vô hướng G được biểu diễn bằng danh sách kể. Hãy viết chương trình cho biết số thành phần liên thông của đô thị G.

Dữ liệu vào: Tệp dothi.txt chứa dữ liệu của đô thị G. 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 cạnh gồm hai đỉnh.

Dữ liệu ra: Số thành phần liên thông của đô thị G.

Lời giải:

Một đô thị G được gọi là không liên thông nếu tổn tại đỉnh u và đỉnh v thuộc G mà không có đường đi giữa hai đỉnh này. Khi đó, đỉnh u và đỉnh v thuộc hai thành phần liên thông khác nhau. Nếu tồn tại đường đi giữa đỉnh u và đỉnh v thì hai đỉnh này phải thuộc cùng một thành phần liên thông. Như vậy, đô thị G không liên thông sẽ có ít nhất hai thành phần liên thông. Yêu cầu: Cho đồ thị vô hướng G được biểu diễn bằng danh sách kể. Viết chương trình cho biết số thành phần liên thông của đô thị G.

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:

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:

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

Trang trước Trang sau

Giải bài tập lớp 12 sách mới các môn học