Giải thuật và lập trình: §2. Biểu diễn đồ thị trên máy tính

2.1. Ma trận liền kề(Ma trận kề)

Giả sử G = (V, E) là một đơn đồ thị có số đỉnh (ký hiệu ⏐V⏐) là n, Không mất tính tổng quát có thể coi các đỉnh được đánh số 1, 2, ..., n. Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông A = [aij] cấp n. Trong đó:

aij = 1 nếu (i, j) ∈ E

aij = 0 nếu (i, j) ∉ E

Quy ước aii = 0 với ∀ i;

Đối với đa đồ thị thì việc biểu diễn cũng tương tự trên, chỉ có điều nếu như (i, j) là cạnh thì không phải ta ghi số 1 vào vị trí aij mà là ghi số cạnh nối giữa đỉnh i và đỉnh j.

Ví dụ:

Các tính chất của ma trận kề:

Đối với đồ thị vô hướng G, thì ma trận kề tương ứng là ma trận đối xứng (aij = aji), điều này không đúng với đồ thị có hướng.

Nếu G là đồ thị vô hướng và A là ma trận kề tương ứng thì trên ma trận A:

Tổng các số trên hàng i = Tổng các số trên cột i = Bậc của đỉnh i = deg(i)

Nếu G là đồ thị có hướng và A là ma trận kề tương ứng thì trên ma trận A:

Tổng các số trên hàng i = Bán bậc ra của đỉnh i = deg+(i)

Tổng các số trên cột i = Bán bậc vào của đỉnh i = deg-(i)

Trong trường hợp G là đơn đồ thị, ta có thể biểu diễn ma trận kề A tương ứng là các phần tử logic.

aij = TRUE nếu (i, j) ∈ E và aij = FALSE nếu (i, j) ∉ E

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

Đơn giản, trực quan, dễ cài đặt trên máy tính

Để kiểm tra xem hai đỉnh (u, v) của đồ thị có kề nhau hay không, ta chỉ việc kiểm tra bằng một phép so sánh: auv ≠ 0.

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

Bất kể số cạnh của đồ thị là nhiều hay ít, ma trận kề luôn luôn đòi hỏi n2 ô nhớ để lưu các phần tử ma trận, điều đó gây lãng phí bộ nhớ dẫn tới việc không thể biểu diễn được đồ thị với số đỉnh lớn.

Với một đỉnh u bất kỳ của đồ thị, nhiều khi ta phải xét tất cả các đỉnh v khác kề với nó, hoặc xét tất cả các cạnh liên thuộc với nó. Trên ma trận kề việc đó được thực hiện bằng cách xét tất cả các đỉnh v và kiểm tra điều kiện auv ≠ 0. Như vậy, ngay cả khi đỉnh u là đỉnh cô lập (không kề với đỉnh nào) hoặc đỉnh treo (chỉ kề với 1 đỉnh) ta cũng buộc phải xét tất cả các đỉnh và kiểm tra điều kiện trên dẫn tới lãng phí thời gian.

2.2. Danh sách cạnh

Trong trường hợp đồ thị có n đỉnh, m cạnh, ta có thể biểu diễn đồ thị dưới dạng danh sách cạnh bằng cách liệt kê tất cả các cạnh của đồ thị trong một danh sách, mỗi phần tử của danh sách là một cặp (u, v) tương ứng với một cạnh của đồ thị. (Trong trường hợp đồ thị có hướng thì mỗi cặp (u, v) tương ứng với một cung, u là đỉnh đầu và v là đỉnh cuối của cung). Danh sách được lưu trong bộ nhớ dưới dạng mảng hoặc danh sách móc nối. Ví dụ với đồ thị ở hình dưới đây:

Hình 1

Cài đặt trên mảng:

Cài đặt trên danh sách móc nối:

Ưu điểm của danh sách cạnh:

Trong trường hợp đồ thị thưa (có số cạnh tương đối nhỏ: chẳng hạn m < 6n), cách biểu diễn bằng danh sách cạnh sẽ tiết kiệm được không gian lưu trữ, bởi nó chỉ cần 2m ô nhớ để lưu danh sách cạnh.

Trong một số trường hợp, ta phải xét tất cả các cạnh của đồ thị thì cài đặt trên danh sách cạnh làm cho việc duyệt các cạnh dễ dàng hơn. (Thuật toán Kruskal chẳng hạn).

Nhược điểm của danh sách cạnh:

Nhược điểm cơ bản của danh sách cạnh là khi ta cần duyệt tất cả các đỉnh kề với đỉnh v nào đó của đồ thị, thì chẳng có cách nào khác là phải duyệt tất cả các cạnh, lọc ra những cạnh có chứa đỉnh v và xét đỉnh còn lại. Điều đó khá tốn thời gian trong trường hợp đồ thị dày (nhiều cạnh).

2.3. Danh sách kề

Để khắc phục nhược điểm của các phương pháp ma trận kề và danh sách cạnh, người ta đề xuất phương pháp biểu diễn đồ thị bằng danh sách kề. Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị, ta cho tương ứng với nó một danh sách các đỉnh kề với v.

Với đồ thị G = (V, E). V gồm n đỉnh và E gồm m cạnh. Có hai cách cài đặt danh sách kề phổ biến:

Hình 2

Cách 1: Dùng một mảng các đỉnh, mảng đó chia làm n đoạn, đoạn thứ i trong mảng lưu danh sách các đỉnh kề với đỉnh i: Với đồ thị ở Hình 54, danh sách kề sẽ là một mảng A gồm 12 phần tử:

Để biết một đoạn nằm từ chỉ số nào đến chỉ số nào, ta có một mảng Head lưu vị trí riêng. Head[i] sẽ bằng chỉ số đứng liền trước đoạn thứ i. Quy ước Head[n + 1] bằng m. Với đồ thị bên thì mảng Head[1..6] sẽ là: (0, 3, 5, 8, 10, 12).

Trong mảng A, đoạn từ vị trí Head[i] + 1 đến Head[i + 1] sẽ chứa các đỉnh kề với đỉnh i. Lưu ý rằng với đồ thị có hướng gồm m cung thì cấu trúc này cần phải đủ chứa m phần tử, với đồ thị vô hướng m cạnh thì cấu trúc này cần phải đủ chứa 2m phần tử Cách 2: Dùng các danh sách móc nối: Với mỗi đỉnh i của đồ thị, ta cho tương ứng với nó một danh sách móc nối các đỉnh kề với i, có nghĩa là tương ứng với một đỉnh i, ta phải lưu lại List[i] là chốt của một danh sách móc nối. Ví dụ với đồ thị ở Hình 2 bên trên, các danh sách móc nối sẽ là:

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

Đối với danh sách kề, việc duyệt tất cả các đỉnh kề với một đỉnh v cho trước là hết sức dễ dàng, cái tên "danh sách kề" đã cho thấy rõ điều này. Việc duyệt tất cả các cạnh cũng đơn giản vì một cạnh thực ra là nối một đỉnh với một đỉnh khác kề nó.

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

Danh sách kề yếu hơn ma trận kề ở việc kiểm tra (u, v) có phải là cạnh hay không, bởi trong cách biểu diễn này ta sẽ phải việc phải duyệt toàn bộ danh sách kề của u hay danh sách kề của v. Tuy nhiên đối với những thuật toán mà ta sẽ khảo sát, danh sách kề tốt hơn hẳn so với hai phương pháp biểu diễn trước. Chỉ có điều, trong trường hợp cụ thể mà ma trận kề hay danh sách cạnh không thể hiện nhược điểm thì ta nên dùng ma trận kề (hay danh sách cạnh) bởi cài đặt danh sách kề có phần dài dòng hơn.

2.4. Nhận xét

Trên đây là nêu các cách biểu diễn đồ thị trong bộ nhớ của máy tính, còn nhập dữ liệu cho đồ thị thì có nhiều cách khác nhau, dùng cách nào thì tuỳ. Chẳng hạn nếu biểu diễn bằng ma trận kề mà cho nhập dữ liệu cả ma trận cấp n x n (n là số đỉnh) thì khi nhập từ bàn phím sẽ rất mất thời gian, ta cho nhập kiểu danh sách cạnh cho nhanh. Chẳng hạn mảng A (nxn) là ma trận kề của một đồ thị vô hướng thì ta có thể khởi tạo ban đầu mảng A gồm toàn số 0, sau đó cho người sử dụng nhập các cạnh bằng cách nhập các cặp (i, j); chương trình sẽ tăng A[i, j] và A[j, i] lên 1. Việc nhập có thể cho kết thúc khi người sử dụng nhập giá trị i = 0.

Ví dụ:

program Nhap_Do_Thi;

var
  A: array[1..100, 1..100] of Integer; {Ma trận kề của đồ thị}
  n, i, j: Integer;
begin
  Write('Number of vertices'); ReadLn(n);
  FillChar(A, SizeOf(A), 0);
  repeat
    Write('Enter edge (i, j) (i = 0 to exit) ');
    ReadLn(i, j); {Nhập một cặp (i, j) tưởng như là nhập danh sách cạnh}
    if i <> 0 then
    begin {nhưng lưu trữ trong bộ nhớ lại theo kiểu ma trận kề}
      Inc(A[i, j]);
      Inc(A[j, i]);
    end;
  until i = 0; {Nếu người sử dụng nhập giá trị i = 0 thì dừng quá trình nhập, nếu không thì tiếp tục}
end.

Trong nhiều trường hợp đủ không gian lưu trữ, việc chuyển đổi từ cách biểu diễn nào đó sang cách biểu diễn khác không có gì khó khăn. Nhưng đối với thuật toán này thì làm trên ma trận kề ngắn gọn hơn, đối với thuật toán kia có thể làm trên danh sách cạnh dễ dàng hơn v.v... Do đó, với mục đích dễ hiểu, các chương trình sau này sẽ lựa chọn phương pháp biểu diễn sao cho việc cài đặt đơn giản nhất nhằm nêu bật được bản chất thuật toán. Còn trong trường hợp cụ thể bắt buộc phải dùng một cách biểu diễn nào đó khác, thì việc sửa đổi chương trình cũng không tốn quá nhiều thời gian.