Question

Đã trả lời bởi chuyên gia

Answer 1

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)

...Xem thêm

Answer 2

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)

1 câu trả lời 11

Câu hỏi hot cùng chủ đề

Bài viết mới nhất Lớp 12