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 ...
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.
Thí dụ 4. của các đồ thị trong hình 1 được mô tả trong hình sau:
Đỉnh đầu
Đỉnh đầu
Hình 2. của đồ thị vô hướng G và có hướng G1 cho trong hình 1
Để ý rằng trong cách biểu diễn này chúng ta cần phải sử dụng cỡ m+n đơn vị bộ nhớ.Trong các thuật toán mô tả ở các phần tiếp theo hai cấu trúc danh sách kề và ma trận trọng số được sử dụng thường xuyên.
