Chưa có bài trả lời

[nguyencan]

Các phép biểu diễn của đồ thị

Có hai cách chuẩn để biểu diễn một đồ thị G=(V,E): dưới dạng một tập hợp các danh sách kề hoặc một ma trận kề. Phép biểu diễn danh sách kề thường được ưa dùng, bởi nó cung cấp một cách nén gọn để biểu diễn các đồ thị thưa (sparse graph, là những đồ thị mà số cạnh |E| nhỏ hơn nhiều so với tập đỉnh bình phương |V|2. Hầu hết các thuật toán về đồ thị được thực hiện nhập dữ liệu và xử lý theo dạng danh sách kề. Tuy nhiên, phép biểu diễn ma trận kề có thể được ưa thích dùng khi đồ thị trù mật (dense, tức là |E| sát với tập đỉnh bình phương |V|2 ) hoặc khi ta cần nhanh chóng biết có một cạnh nối hai đỉnh đã cho hay không. Ví dụ bài toán tìm lộ trình ngắn nhất với tất cả các cặp đỉnh thì có thể dùng đồ thị nhập liệu dạng ma trận kề. Tuy nhiên trong bài toán tìm cây khung tối thiểu theo thuật toán PRIM thì danh sách kề sẽ được đề nghị sử dụng tốt hơn.

Phép biểu diễn danh sách kề (adjacency-list representation) của một đồ thị G=(V,E) bao gồm một mảng Adj gồm |V| danh sách, một cho từng đỉnh V. Với từng đỉnh u thuộc V, danh sách kề Adj[u] chứa trỏ đến tất cả các đỉnh v sao cho có một cạnh (u,v) thuộc E. Nghĩa là, Adj[u] bao gồm tất cả các đỉnh kề với u trong G. Các đỉnh trong danh sách kề thường được lưu trữ theo thứ tự tuỳ ý.

Dưới đây mô tả việc lưu trữ một đồ thị vô hướng, không trọng số dưới dạng danh sách kề và ma trận kề.

G1=(V,E), V={1,2,3,4,5}, E={12,15,23,24,25,34,54} (cách viết: 12 cạnh nối đỉnh 1 và 2, 15 cạnh nối đỉnh 1 và đỉnh 5,....)

Danh sách kề được thể hiện đơn giản như sau:

1)---2----5

2)---1----3----4----5

3)---2---4

4)---2----5

5)---1----4

Ma trận kề được thể hiện như sau:

0 1 0 0 1

1 0 1 1 1

0 1 0 1 0

0 1 1 0 1

1 1 0 1 0

======================
Các bạn xem giùm, nếu có ý tưởng khác post lên nhé

Với đồ thị vô hướng có trọng số thì khi lưu trữ đồ thị dưới dạng ma trận kề thì các số 1 ở trên được thay bằng trọng số cạnh tương ứng, còn đối với danh sách kề thì mỗi nút sẽ gồm 2 giá trị giá trị đỉnh và giá trị trọng số cạnh tương ứng.



Dưới đây minh hoạ biểu diễn một đồ thị trọng số dưới dạng hai cấu trúc:

G2=(V,E), với V={1,2,3,4,5,6}, E={12(33),13(17),23(18),24(20),34(16),35(4), 45(9),46(8),56(14)}

(Cách viết 12(33) cạnh nối đỉnh 1 và đỉnh 2 có trọng số là 33)

Danh sách kề của đồ thị G2:

1)------2/33-------3/17

2)------1/33-------3/18------4/20

3)------1/17-------2/18------4/16-----5/4

4)------2/20-------3/16------5/9------6/8

5)-------3/4-------4/9--------6/14

6)-------4/8-------5/14



Ma trận trọng số dạng danh sách kề của G2 như sau:

0 33 17 0 0 0

33 0 18 20 0 0

17 18 0 16 4 0

0 20 16 0 9 8

0 0 4 9 0 14

0 0 0 8 14 0