Ma trận kề là gì? biểu diễn đồ thị bằng ma trận kề và danh sách kề 2023

Đối với đồ thị thưa, nghĩa là đồ thị có ít cạnh, người ta thường chọn dùng danh sách kề hơn do nó chiếm ít bộ nhớ hơn. Ma trận liên thuộc là một biểu diễn ma trận khác cho đồ thị.

Quan hệ giữa một đồ thị và ma trận kề của nó được nghiên cứu trong lý thuyết phổ đồ thị (spectral graph theory)^[1].

Khái niệm

Ma trận kề là cách biểu diễn đồ thị G = {V, E} dưới dạng ma trận các giá trị boolean.

Biểu diễn ma trận kề: Kích thước của ma trận là VxV trong đó V là số đỉnh trong đồ thị và giá trị của một đầu vào Aij là 1 hoặc 0 tùy thuộc vào việc có một cạnh từ đỉnh i đến đỉnh j hay không.

Ví dụ về ma trận kề

Hình ảnh dưới đây sẽ biểu diễn một đồ thị và ma trận kề tương đương của nó.

Trong trường hợp đồ thị vô hướng, ma trận sẽ đối xứng qua đường chéo vì với mỗi cạnh (i, j) thì cũng sẽ có một cạnh (j, i) tương ứng.

Ưu điểm của ma trận kề

• Các phép toán cơ bản như thêm một cạnh, xóa một cạnh và kiểm tra xem có cạnh nào từ đỉnh i đến đỉnh j hay không là các thao tác hiệu quả về mặt thời gian và thời gian là không đổi.
• Nếu đồ thị dày đặc và số lượng cạnh lớn, ma trận kề sẽ là lựa chọn đầu tiên. Ngay cả khi đồ thị và ma trận kề là thưa, chúng ta có thể biểu diễn nó bằng cách sử dụng cấu trúc dữ liệu cho ma trận thưa.
• Tuy nhiên, lợi thế lớn nhất đến từ việc sử dụng ma trận. Những tiến bộ gần đây trong phần cứng cho phép chúng ta thực hiện các phép toán với ma trận lớn trên GPU.
• Bằng cách thực hiện các thao tác trên ma trận kề, chúng ta có thể có được những hiểu biết quan trọng về bản chất của đồ thị và mối quan hệ giữa các đỉnh của nó.

Nhược điểm của ma trận kề

Yêu cầu về không gian VxV của ma trận kề làm cho nó trở thành một đối tượng tiêu thụ lượng bộ nhớ lớn. Các đồ thị thường sẽ không có quá nhiều liên kết và đây là lý do chính tại sao danh sách kề là lựa chọn tốt hơn cho hầu hết các nhiệm vụ.

Trong khi các thao tác cơ bản được thực hiện dễ dàng, nhưng các thao tác như inEdges và outEdges sẽ rất tốn kém khi sử dụng biểu diễn ma trận kề.

Ví dụ:

#include <stdio.h>
#define V 6

void init(int arr[][V]) {
  for (int i = 0; i < V; i++)
    for (int j = 0; j < V; j++)
      arr[i][j] = 0;
}

void add_edge(int arr[][V], int i, int j) {
  arr[i][j] = 1;
  arr[j][i] = 1;
}

void print(int arr[][V]) {
  for (int i = 0; i < V; i++) {
    printf("%d: ", i);
    for (int j = 0; j < V; j++) {
      printf("%d ", arr[i][j]);
    }
    printf("\n");
  }
}

int main() {
  int matrix[V][V];
  init(matrix);
  add_edge(matrix, 2, 3);
  add_edge(matrix, 2, 4);
  add_edge(matrix, 3, 4);
  add_edge(matrix, 4, 2);
  add_edge(matrix, 4, 5);
  print(matrix);
  return 0;
}

Kết quả:

0: 0 0 0 0 0 0 
1: 0 0 0 0 0 0 
2: 0 0 0 1 1 0 
3: 0 0 1 0 1 0 
4: 0 0 1 1 0 1 
5: 0 0 0 0 1 0

Ứng dụng của ma trận gần kề:

• Tạo bảng định tuyến trong mạng.
• Các bài toán về tìm hướng đi hoặc định vị.

Danh sách kề

Danh sách kề biểu thị một biểu đồ dưới dạng một mảng các danh sách được liên kết. Chỉ số của mảng đại diện cho một đỉnh và mỗi phần tử 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 với đỉnh đó.

Biểu đồ và biểu diễn danh sách kề tương đương của nó được biểu diễn trong hình bên dưới.

Danh sách kề có hiệu quả về mặt lưu trữ 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 có hàng triệu đỉnh và cạnh, điều này có nghĩa là rất nhiều không gian sẽ được tiết kiệm.

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

Danh sách kề đơ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 sẽ cùng 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ẽ sử dụng một đồ thị không có nhãn 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.

Ta sẽ cùng tìm hiểu các cấu trúc tại đây.

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

Điều chúng ta muốn là lưu trữ một con trỏ tới struct node*. Điều này là do chúng ta không biết đồ thị sẽ có bao nhiêu đỉnh và vì vậy chúng ta không thể tạo một mảng danh sách liên kết tại thời điểm biên dịch.

Danh sách kề bằng ngôn ngữ C++

Nó là cùng một cấu trúc nhưng bằng cách sử dụng cấu trúc dữ liệu STL danh sách có sẵn của C ++, chúng ta làm cho cấu trúc trông trở nên gọn hơn. Chúng ta cũng có thể tóm tắt các chi tiết của việc thực hiện.

class Graph
{
    int numVertices;
    list<int> *adjLists;
public:
    Graph(int V);
    void addEdge(int src, int dest);
};

Ví dụ: Triển khai danh sách kề bằng ngôn ngữ lập trình C.

#include <stdio.h>
#include <stdlib.h>

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

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

struct node* create_node(int v) {
  struct node* new_node = malloc(sizeof(struct node));
  new_node->vertex = v;
  new_node->next = NULL;
  return new_node;
}

struct Graph* create_graph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;
  graph->adjLists = malloc(vertices * sizeof(struct node*));
  for(int i = 0; i < vertices; i++)
    graph->adjLists[i] = NULL;

  return graph;
}

void add_edge(struct Graph* graph, int s, int d) {
  struct node* new_node = create_node(d);
  new_node->next = graph->adjLists[s];
  graph->adjLists[s] = new_node;
  new_node = create_node(s);
  new_node->next = graph->adjLists[d];
  graph->adjLists[d] = new_node;
}

void print(struct Graph* graph) {
  for (int v = 2; v < graph->numVertices; v++) {
    struct node* temp = graph->adjLists[v];
    printf("\nĐỉnh %d\n: ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}

int main() {
  struct Graph* graph = create_graph(6);
  add_edge(graph, 2, 3);
  add_edge(graph, 2, 4);
  add_edge(graph, 2, 5);
  add_edge(graph, 3, 4);
  print(graph);
  return 0;
}

Kết quả:

Đỉnh 2
: 5 -> 4 -> 3 -> 
Đỉnh 3
: 4 -> 2 -> 
Đỉnh 4
: 3 -> 2 -> 
Đỉnh 5
: 2 ->

Trên đây là khái niệm và ví dụ cơ bản về ma trận kề và danh sách kề. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!

Tham khảo[sửa | sửa mã nguồn]

Tài liệu[sửa | sửa mã nguồn]

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 22.1: Representations of graphs, pp. 527–531.

Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Ma trận kề.