Adjacency list là gì?

Danh sách kề (adjacency list) biểu thị một đồ thị (graph) dưới dạng một mảng (array) các danh sách được liên kết (linked list). Chỉ số (index) của mảng đại diện cho một đỉnh (vertex) và mỗi phần tử (element) trong danh sách liên kết của nó đại diện cho các đỉnh khác tạo thành một cạnh (edge) với đỉnh.

Ví dụ chúng ta có một đồ thị bên dưới.

Chúng ta có thể biểu diễn đồ thị này dưới dạng danh sách liên kết trên máy tính như hình bên dưới.

Ở đây 0, 1, 2, 3 là các đỉnh và mỗi đỉnh tạo thành một danh sách liên kết với tất cả các đỉnh liền kề ( adjacent vertices) của nó. Ví dụ đỉnh 1 có hai đỉnh kề nhau là 0 và 2. Do đó 1 được liên kết với 0 và 2 trong hình trên.

Ưu điểm:

• Danh sách kề hiệu quả về mặt lưu trữ (storage) vì chúng ta chỉ cần lưu trữ các giá trị cho các cạnh. Đối với một đồ thị thưa (sparse graph) có hàng triệu đỉnh và cạnh, điều này có nghĩa là tiết kiệm được rất nhiều không gian (space).
• Nó cũng giúp tìm tất cả các đỉnh kề với một đỉnh một cách dễ dàng.

Nhược điểm

• Tìm danh sách kề (adjacent list) không nhanh hơn ma trận kề (adjacency matrix) vì tất cả các nút (node) được kết nối trước tiên phải được truy cập để tìm chúng.

Cấu trúc của danh sách kề (adjacency list):

Danh sách kề adjacency list đơn giản nhất cần có cấu trúc dữ liệu nút để lưu một đỉnh và cấu trúc dữ liệu đồ thị để tổ chức các nút. Chúng ta tiếp cận với định nghĩa cơ bản của đồ thị - tập hợp các đỉnh và cạnh {V, E}. Để đơn giản, chúng ta sử dụng một đồ thị không có nhãn (label) thay vì một đồ thị có nhãn, tức là các đỉnh được xác định bởi các chỉ số 0,1,2,3 của chúng.

struct node{
    int vertex;
    struct node* next;
};

struct Graph{
    int numVertices;
    struct node** adjLists;
};

Code danh sách kề trong C:

// Adjascency List representation in C

#include 
#include 

struct node {
  int vertex;
  struct node* next;
};
struct node* createNode(int);

struct Graph {
  int numVertices;
  struct node** adjLists;
};

// Create a node
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// Create a graph
struct Graph* createAGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));

  int i;
  for (i = 0; i adjLists[i] = NULL;

  return graph;
}

// Add edge
void addEdge(struct Graph* graph, int s, int d) {
  // Add edge from s to d
  struct node* newNode = createNode(d);
  newNode->next = graph->adjLists[s];
  graph->adjLists[s] = newNode;

  // Add edge from d to s
  newNode = createNode(s);
  newNode->next = graph->adjLists[d];
  graph->adjLists[d] = newNode;
}

// Print the graph
void printGraph(struct Graph* graph) {
  int v;
  for (v = 0; v numVertices; v++) {
    struct node* temp = graph->adjLists[v];
    printf("\n Vertex %d\n: ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}

int main() {
  struct Graph* graph = createAGraph(4);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 0, 3);
  addEdge(graph, 1, 2);

  printGraph(graph);

  return 0;
}

Ứng dụng của danh sách kề (adjacency list):

Sẽ nhanh hơn khi sử dụng danh sách kề (adjacency list) cho các đồ thị có số cạnh ít hơn....