Danh_sách_kề
Danh_sách_kề

Danh_sách_kề

Trong lý thuyết đồ thị, danh sách kề (tiếng Anh: adjacency list) là danh sách biểu diễn tất cả các cạnh hoặc cung trong một đồ thị.Nếu đồ thị vô hướng, mỗi phần tử của danh sách là một cặp hai đỉnh là hai đầu của cạnh tương ứng. Nếu đồ thị có hướng, mỗi phần tử là một cặp có thứ tự gồm hai đỉnh là đỉnh đầu và đỉnh cuối của cung tương ứng.Ví dụ, danh sách {a,b},{a,c},{b,c} mô tả đồ thị vô hướng trong hình dưới đây, trong đó ba đỉnh a, b, c được nối với nhau.Thông thường, danh sách kề không coi trọng thứ tự giữa các cạnh.Trong Khoa học máy tính, danh sách kề là một cấu trúc dữ liệu gắn bó chặt chẽ với việc biểu diễn đồ thị. Trong một biểu diễn danh sách kề, với mỗi đỉnh trong đồ thị, ta lưu trữ tất cả các đỉnh khác có cạnh nối với đỉnh đó - danh sách kề của đỉnh. Ví dụ, đồ thị trong hình vẽ có biểu diễn danh sách kề như sau: