Giải thuật và lập trình - C: III. Biều diễn đồ thị


Đăng ký nhận thông báo về những video mới nhất

Một số cấu trúc dữ liệu có thể dùng để biểu diễn đồ thị. Việc chọn cấu trúc dữ liệu nào là tuỳ thuộc vào các phép toán trên các cung và đỉnh của đồ thị. Hai cấu trúc thường gặp là biểu diễn đồ thị bằng ma trận kề (adjacency matrix) và biểu diễn đồ thị bằng danh sách các đỉnh kề (adjacency list).

1. Biểu diễn đồ thị bằng ma trận kề

Ta dùng một mảng hai chiều, chẳng hạn mảng A, kiểu boolean để biểu diễn các đỉnh kề. Nếu đồ thị có n đỉnh thì ta dùng mảng A có kích thước nxn. Giả sử các đỉnh được đánh số 1..n thì A[i,j] = true, nếu có đỉnh nối giữa đỉnh thứ i và đỉnh thứ j, ngược lại thì A[i,j] = false. Rõ ràng, nếu G là đồ thị vô hướng thì ma trận kề sẽ là ma trận đối xứng. Chẳng hạn đồ thị V.1b có biểu diễn ma trận kề như sau:

Ta cũng có thể biểu diễn true là 1 còn false là 0. Với cách biểu diễn này thì đồ thị hình V.1a có biểu diễn ma trận kề như sau:

Với cách biểu diễn đồ thị bằng ma trận kề như trên chúng ta có thể định nghĩa chỉ số của đỉnh là số nguyên chỉ đỉnh đó (theo cách đánh số các đỉnh) và ta cài đặt các phép toán FIRST, NEXT và VERTEX như sau:

const null=0;
int A[n,n]; //mảng biểu diễn ma trận kề
int FIRST(int v){ //trả ra chỉ số [1..n] của đỉnh đầu tiên kề với v từ 1..n
  int i;
  for (i=1; i<=n; i++)
    if (a[v-1,i-1] == 1)
      return (i);   //trả ra chỉ số đỉnh của đồ thị return (null);
}

int NEXT(int v; int i){ //trả ra đỉnh [1..n] sau đỉnh i mà kề với v; i, v Î 1..n
  int j;
  for (j=i+1; j<=n; j++)
    if (a[v-1,j-1] == 1)
      return(j);
  return(null);
}

Còn VERTEX(i) chỉ đơn giản là trả ra chính i.

Vòng lặp trên các đỉnh kề với v có thể cài đặt như sau:

i=FIRST(v);
while (i<>null){
  w = VERTEX(i);
  //thao tác trên w i =NEXT(v,i);
}

Trên đồ thị có nhãn thì ma trận kề có thể dùng để lưu trữ nhãn của các cung chẳng hạn cung giữa i và j có nhãn a thì A[i,j]=a. Ví dụ ma trận kề của đồ thị hình V.2 là:

Ở đây các cặp đỉnh không có cạnh nối thì ta để trống, nhưng trong các ứng dụng ta có thể phải gán cho nó một giá trị đặc biệt nào đó để phân biệt với các giá trị có nghĩa khác. Chẳng hạn như trong bài toán tìm đường đi ngắn nhất, các giá trị số nguyên biểu diễn cho khoảng cách giữa hai thành phố thì các cặp thành phố không có cạnh nối ta gán cho nó khoảng cách bằng µ, còn khoảng cách từ một đỉnh đến chính nó là 0.

Cách biểu diễn đồ thị bằng ma trận kề cho phép kiểm tra một cách trực tiếp hai đỉnh nào đó có kề nhau không. Nhưng nó phải mất thời gian duyệt qua toàn bộ mảng để xác định tất cả các cạnh trên đồ thị. Thời gian này độc lập với số cạnh và số đỉnh của đồ thị. Ngay cả số cạnh của đồ thị rất nhỏ chúng ta cũng phải cần một mảng nxn phần tử để lưu trữ. Do vậy, nếu ta cần làm việc thường xuyên với các cạnh của đồ thị thì ta có thể phải dùng cách biểu diễn khác cho thích hợp hơn.

2. Biểu diễn đồ thị bằng danh sách các đỉnh kề:

Trong cách biểu diễn này, ta sẽ lưu trữ các đỉnh kề với một đỉnh i trong một danh sách liên kết theo một thứ tự nào đó. Như vậy ta cần một mảng HEAD một chiều có n phần tử để biểu diễn cho đồ thị có n đỉnh. HEAD[i] là con trỏ trỏ tới danh sách các đỉnh kề với đỉnh i. ví dụ đồ thị hình V.1a có biểu diễn như sau:


Mảng HEAD


Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!