Nhiệm vụ. Đếm số thành phần liên thông của đồ thị trang 76 Chuyên đề Tin học 12
Nhiệm vụ. Đếm số thành phần liên thông của đồ thị
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
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: