Danh sách kề (Adjacency list)

Bài số 10 trong 10 bài của khóa học Cấu trúc dữ liệu

Trong bài viết này, bạn sẽ cùng Lập Trình Không Khó tìm hiểu về danh sách kề (tiếng anh: adjacency list). Bài viết sẽ trình bày từng bước chi tiết để bạn đọc có thể hiểu được cấu trúc dữ liệu danh sách kề, phân tích ưu nhược điểm và ứng dụng của nó. Cũng trong bài viết này, chúng ta sẽ cùng nhau đi cài đặt cấu trúc danh sách kề sử dụng ngôn ngữ C/C++.

Để nắm được kiến thức của bài viết này, bạn nên có kiến thức về:

Chúng ta cùng đi tìm hiểu về danh sách kề nào!

Danh sách kề là gì?

Danh sách kề (Adjacency list) biểu diễn một đồ thị (graph) dưới dạng một mảng các danh sách liên kết. Trong đó, chỉ số mảng đại diện cho đỉnh của đồ thị và các phần tử trong danh sách liên kết của đỉnh đó là cách đỉnh có kết nối với đỉnh đó.

Lấy ví dụ với một đồ thị dưới đây:

Ví dụ về đồ thị vô hướng
Ví dụ một đồ thị vô hướng

Với đồ thị phía trên, chúng ta có thể biểu diễn nó vào bộ nhớ máy tính dưới dạng một mảng các danh sách liên kết như hình vẽ dưới đây:

Biểu diễn đồ thị phía trên dưới dạng mảng của các danh sách liên kết
Biểu diễn đồ thị phía trên dưới dạng mảng của các danh sách liên kết

Đồ thị của chúng ta có 4 đỉnh (0, 1, 2 và 3). Do đó, chúng ta cũng sẽ có 4 danh sách liên kết cho 4 đỉnh đó. Trong mỗi danh sách liên kết là các Node đại diện cho các đỉnh có liên kết với Node head.

Ví dụ:

  • Danh sách liên kết cho đỉnh 0 (head) có 3 Node phía sau lần lượt là (1, 2 và 3) thể hiện rằng các cặp đỉnh (0, 1), (0,2) và (0, 3) có kết nối.
  • Tương tự, danh sách liên kết của đỉnh 2 (head) có 2 Node phía sau lần lượt là (0 và 2) thể hiện rằng các cặp đỉnh (2, 0) và (2,1) có kết nối.

Ưu điểm của danh sách kề

  • So với ma trận kề (adjacency matrix), biểu diễn đồ thị dưới dạng danh sách kề giúp tiết kiệm bộ nhớ hơn. Ta sẽ thấy rõ điều này khi biểu diễn đồ thị có số lượng lớn đỉnh nhưng có ít số cạnh (kết nối).
  • Việc duyệt các đỉnh kề với một đỉnh nào đó cũng cực kỳ nhanh chóng do mỗi đỉnh chỉ kết nối tới các đỉnh kề với nó.

Nhược điểm của danh sách kề

  • Do sử dụng danh sách liên kết, việc kiểm tra 2 đỉnh bất kỳ có kết nối hay không cần phải duyệt tuần tự từ node head, sẽ chậm hơn so với việc kiểm tra nếu cài đặt bằng ma trận kề.

Cài đặt danh sách kề

Để đơn giản, mục hướng dẫn cài đặt này chúng ta sẽ làm việc với:

  • Đồ thị vô hướng và không có trọng số
  • Danh sách liên kết đơn

# Cấu trúc của danh sách kề

Do danh sách kề là mảng của các danh sách liên kết, nên chúng ta cần định nghĩa cấu trúc Node cho các phần tử của danh sách liên kết:

Ngoài ra, chúng ta cũng cần định nghĩa cấu trúc đồ thị: mảng của các danh sách liên kết với số lượng đỉnh cho trước:

Chúng ta sử dụng con trỏ cấp 2 struct Node** lists là bởi vì nó là một mảng của các danh sách liên kết. Mà mỗi danh sách liên kết lại là một con trỏ kiểu Node.

Sau này, khi biết số lượng đỉnh thì chúng ta sẽ cấp phát bộ nhớ động cho nó đủ mức nó sử dụng.

# Các hàm khởi tạo

Chúng ta sẽ cần hàm khởi tạo Node cho danh sách liên kết để mỗi khi cần thêm Node vào danh sách liên kết thì ta có thể gọi tới và sử dụng:

  • Cấp phát bộ nhớ cho Node
  • Gán giá trị đỉnh cho Node đó
  • Cho next của nó trỏ tới NULL, tránh nó trỏ lung tung (giá trị rác)

Và đương nhiên không thể thiếu, chúng ta cần 1 hàm để khởi tạo cho đồ thị. Hàm này sẽ thực thi các việc sau:

  • Cấp phát bộ nhớ cho đồ thị
  • Cấp phát bộ nhớ cho mảng các danh sách liên kết của đồ thị
  • Khởi tạo đỉnh ban đầu cho mỗi DSLK

# Tạo kết nối giữa 2 đỉnh

Nếu 2 đỉnh ds có kết nối với nhau, ta sẽ thêm Node d vào danh sách liên kết có đỉnh là s và ngược lại.

# Duyệt danh sách kề

Việc duyệt danh sách kề thực chất là việc lặp lại của thao tác duyệt danh sách liên kết đơn.

# Source code danh sách kề đầy đủ

Sau cùng, chúng ta sẽ bổ sung hàm main và thử thực thi chương trình. Dưới đây là toàn bộ source code cài đặt danh sách kề:

Trong hàm main, mình sẽ biểu diễn 1 đồ thị 4 đỉnh và có các kết nối như hình vẽ ở ví dụ phía trên. Và đây là kết quả khi chạy trương chình (tên file code mình để là adj.c):

Biểu diễn danh sách sinh viên

Về bản chất, danh sách kề là cấu trúc dữ liệu để biểu diễn đồ thị vào bộ nhớ máy tính. Nên chính xác thì ta nên nói ứng dụng của đồ thị.

Ở mục này, mình chia sẻ thêm 1 source code sử dụng danh sách kề để biểu diễn mối quan hệ giữa các sinh viên theo lớp học: Các sinh viên cùng lớp sẽ có kết nối với nhau.

Các bạn có thể tham khảo học tập, mình xin phép không giải thích thêm.

Kết quả thực thi:

Bài viết tới đây là kết thúc, xin chào và hẹn gặp lại các bạn ở các bài hướng dẫn tiếp theo!

Theo dõi Lập Trình Không Khó để không bỏ lỡ các bài học bổ ích:

Các bài viết trong khóa họcBài trước: Bài tập danh sách liên kết đơn tổng hợp
Sáng lập cộng đồng Lập Trình Không Khó với mong muốn giúp đỡ các bạn trẻ trên con đường trở thành những lập trình viên tương lai. Tất cả những gì tôi viết ra đây chỉ đơn giản là sở thích ghi lại các kiến thức mà tôi tích lũy được.
Subscribe
Notify of
guest
0 Bình luận
Inline Feedbacks
View all comments