Làm sao để cài đặt 1 đồ thị bằng danh sách liên kết?

[Hieu_Ngo_Minh (Hiếu Ngô Minh)]

Việc cài đặt 1 đồ thị bằng ma trận hay danh sách kề đối với e thì ok . Nhưng mà cài đặt = 1 danh sách liên kết thì e lại lấy khó thực hiện quá ạ . Ví dụ 1 đỉnh nối với N đỉnh khác thì mình phải tạo ra N con trỏ để nối với những đỉnh đó ? Mong mọi người có thể cho e ý tưởng với ạ

[noname00 (HK boy)]

Danh sách kề thì cũng là mảng 1 danh sách liên kết thôi. Ở dạng cổ điển thì người ta cài danh sách kề bằng danh sách liên kết.

// adjacent_list là adjacent list (danh sách kề),
// a[x] chứa tất cả các đỉnh y mà có cạnh nối x -> y
struct linked_list {
    ...
};

linked_list adjacent_list[N]; // N là hằng số
// hoặc
vector<linked_list> adjacent_list;

Tổng độ phức tạp không gian của adjacent list là O(n).