Các phương pháp lưu trữ đồ thị

Ma trận kề. Ma trận trọng số

Xét đơn đồ thị vô hướng G =(V,E), với tập đỉnh V={1, 2,. . . ,n} , tập cạnh E= {e₁, e₂, . . . ,e_m }. Ta gọi ma trận kề của đồ thị G là ma trận.

A=( a_i,j : i, j = 1, 2, . . . ,n)

Với các phần tử được xác định theo qui tắc sau đây:

a_{i, j} = 0, nếu (i, j) ∈ E và

a_i,j = 1 , nếu (i, j) ∈ E, i, j =1, 2,. . ., n.

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

1) Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là

a[i,j]=a[j,i], i,j =1,2,. . .,n. Ngược lại, mỗi (0,1)-ma trận đối xứng cấp n sẽ tương ứng, chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đơn đồ thị vô hướng n đỉnh.

2) Tổng các phần từ trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j).

3) nếu ký hiệu a_ịj^p , i,j=1, 2,. . . ,n là phần tử của ma trận A^p =A.A. . .A p thừa số. Khi đó a_ịj^p , i,j=1, 2,. . . ,n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian.

Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự.

Danh sách cạnh (cung)

Trong trường hợp đồ thị thưa (đồ thị có số cạnh m thoả mãn bất dẳng thức: m < 6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng danh sách cạnh.

Trong cách biểu diễn đồ thị bởi danh sách cạnh (cung) chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Một cạnh (cung) e = (x,y) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. như vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cách biểu diễn này là để xác định những đỉnh nào của đồ thị là kề với một đỉnh cho trước chúng ta phải làm cỡ m phép so sánh (khi duyệt qua danh sách tất cả các cạnh của đồ thị).

Chú ý: Trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để lưu trữ trọng số của các cạnh.

Danh sách kề

Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dưới dạng danh sách kề là cách biểu diễn thích hợp nhất được sử dụng.

Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với nó, mà ta sẽ ký hiệu là

Ke(v)= { u ∈ V: (v,u)∈ E }

Khi đó vòng lặp thực hiện với mỗi một phần tử trong danh sách này theo thứ tự các phần tử được sắp xếp trong nó sẽ được viết như sau:

for u ∈ Ke(v) do. . .

Chẳng hạn, trên PASCAL có thể mô tả danh sách này như sau (Gọi là cấu trúc Forward Star):

Const

m=1000; {m-so canh}

n= 100; {n-so dinh}

var

Ke: array[1..m] of integer;

Tro: array[1..n+1] of integer;

Trong đó Tro[i] ghi nhận vị trí bắt đầu của danh sách kề của đỉnh i, i=1, 2,. . .,n, Tro[n+1]=2m+1.

Khi đó dòng lệnh qui ước

for u ∈ Ke(v) do

begin . . . end.

Có thể thay thế bởi cấu trúc lệnh cụ thể trên PASCAL như sau

For i:=Tro[v] to Tro[v+1]-1 do

Begin

U:=Ke[i];

. . . .

End;

Trong rất nhiều thuật toán làm việc với đồ thị chúng ta thường xuyên phải thực hiện các thao tác: Thêm hoặc bớt một số cạnh. Trong trường hợp này cấu trúc dữ liệu dùng ở trên là không thuận tiện. Khi đó nên chuyển sang sử dụng danh sách kề liên kết (Linked Adjancency List) như mô tả trong chương trình nhập danh sách kề của đồ thị từ bàn phím và đưa danh sách đó ra màn hình sau đây:

Program AdjList;

Const

maxV=100;

Type

link=^node;

node=record

v:integer;

next:link;

End;

Var

j,x,y,m,n,u,v:integer;

t:link;

Ke:array[1. .Vmax] of link;

Begin

Write(‘Cho so canh va dinh cua do thi:’); readln(m,n);

(*Khoi tao*)

for j:=1 to n do Ke[j]:=nil;

for j:=1 to m do

begin

write(‘Cho dinh dau va cuoi cua canh ‘,j,’:’);

readln(x,y);

new(t); t^.v:=x, t^.next:=Ke[y]; Ke[y]:=t;

new(t); t^.v:=y, t^.next:=Ke[x]; Ke[x]:=t;

end;

writeln(‘Danh sach ke cua cac dinh cua do thi:’);

for J:=1 to m do

begin

writeln(‘Danh sachcac dinh ke cua dinh ‘,j,’:’);

t:=Ke[j];

while t^.next<>nil do

begin

write(t^.v:4);

t:=t^.next;

end;

end;

readln;

End.