Ta có:
n là cạnh ma trận
ls là ma trận đã nhận được đã kiểm đúng format
label là danh sách n bit nhị phân làm nhãn cho n đỉnh
connected_components là danh sách các thành phần liên thông kiểu dict với:
key là đỉnh hiện tại
value là đỉnh liên thông tiếp theo (nếu không còn đỉnh nào khác liên thông với key thì value là null)
number_of_connected_components = [0] là số thành phần liên thông, đặt kiểu list để có thể thay đổi giá trị trực tiếp
Gán nhãn 0 cho tất cả đỉnh
Duyệt n đỉnh và đặt đỉnh đang xét là Vertex:
Nếu đỉnh chưa duyệt (label[Vertex) == 0) thì gọi visit đỉnh đó
Trong visit: Tham số hình thức là ver (đỉnh đang xét)
Ta đánh dấu đỉnh này đã duyệt
Duyệt n đỉnh với i:
Nếu i trùng ver hoặc i đã từng được duyệt (label[i] == 1) thì bỏ qua và đến i kế tiếp
Ngược lại thì:
Nếu đỉnh i nào không có đường đi tới ver (ls[ver][i] == 0) thì bỏ qua và đến i kế tiếp
Ngược lại thì:
thêm key ver có value là i vào connected_components
gọi đệ quy Visit với tham số truyền vào là i và thực hiện lại Visit đỉnh i
Ngược lại nếu đã duyệt hết đỉnh (đã kết thúc vòng lặp) mà chưa tìm ra đỉnh thích hợp tiếp theo thì:
Thêm key ver có value là 'null' vào connected_components
Kết thúc 1 lần lặp trong điều kiện thỏa (label[Vertex] == 0) thì tăng number_of_connected_components lên 1
Sau thuật toán:
Hiển thị number_of_connected_components lên màn hình
Hiển thị danh sách connected_components
Dữ liệu vào dự kiến:
7
0 1 0 0 0 0 1
1 0 1 0 0 0 0
0 1 0 0 0 0 1
0 0 0 0 1 0 0
0 0 0 1 0 1 0
0 0 0 0 1 0 0
1 0 1 0 0 0 0
Dữ liệu ra dự kiến (chưa dùng đến hàm xuất dữ liệu ra file):
2
{ 0:1, 1:2, 2:6, 6:null, 3:4, 4:5, 5:null }
Đây là kết quả in ra màn hình number_of_connected_components và danh sách connected_components
MỌI NGƯỜI XEM GIÚP MÌNH TỔ CHỨC DỮ LIỆU THẾ NÀY ĐÚNG CHƯA? NẾU CHƯA THÌ NÊN TỔ CHỨC THẾ NÀO MỚI ĐÚNG?
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?