Bài giảng Toán rời rạc 2 - Chương 2: Biểu diễn đồ thị trên máy tính

BIỂU DIỄN ĐỒ THỊ TRÊN
MÁY TÍNH
Toán rời rạc 2
Nội dung
• Biểu diễn đồ thị bằng ma trận kề 
• Biểu diễn đồ thị bằng ma trận liên thuộc 
• Biểu diễn đồ thị bằng danh sách cạnh 
• Biểu diễn đồ thị bằng danh sách kề
2
Biểu diễn đồ thị bằng ma trận kề
Ma trận kề của đồ thị vô hướng
• Xét đồ thị đơn vô hướng G =, với tập đỉnh V = {1, 
2, . . ., n}, tập cạnh E = {e1, e2,.., em}. Ta gọi ma trận kề 
của đồ thị G là ma trận có các phần tử hoặc bằng 0 
hoặc bằng 1 theo qui định như sau:
4
Tính chất ma trận kề đối với đồ thị vô 
hướng
5
Ma trận kề của đồ thị có hướng
• Định nghĩa hoàn toàn tương tự với đồ thị vô 
hướng
– Cần lưu ý tới hướng của cạnh
– Ma trận kề của đồ thị có hướng là không đối xứng
6
Tính chất của ma trận kề của đồ thị có 
hướng
7
Ma trận trọng số
8
Ưu & nhược điểm của ma trận kề
• Ưu điểm 
– Đơn giản, dễ cài đặt trên máy tính 
– Sử dụng một mảng hai chiều để biểu diễn ma trận kề 
– Dễ dàng kiểm tra được hai đỉnh u,v có kề với nhau hay không 
– Đúng một phép so sánh (a*u+*v+≠0?) 
• Nhược điểm 
– Lãng phí bộ nhớ: bất kể số cạnh nhiều hay ít ta cần n2 đơn vị bộ 
nhớ để biểu diễn 
– Không thể biểu diễn được với các đồ thị có số đỉnh lớn 
– Để xem xét đỉnh đỉnh u có những đỉnh kề nào cần mất n phép so 
sánh kể cả đỉnh u là đỉnh cô lập hoặc đỉnh treo
9
Qui ước khuôn dạng lưu trữ ma 
trận kề
• Dòng đầu tiên ghi lại số đỉnh của đồ thị
• N dòng kế tiếp ghi lại ma trận kề của đồ thị.
– Hai phần tử khác nhau của ma trận kề được viết cách 
nhau một vài khoảng trống.
10
Biểu diễn đồ thị bằng ma trận 
liên thuộc
Ma trận liên thuộc: Đồ thị vô hướng
12
Ma trận liên thuộc: Đồ thị có hướng
13
Biểu diễn đồ thị bằng danh sách 
cạnh
Danh sách cạnh (cung)
• Trong trường hợp đồ thị thưa (đồ thị có số cạnh m 6n), 
người ta thường biểu diễn đồ thị dưới dạng danh sách 
cạnh.
– Ta lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng 
(có hướng). Mỗi cạnh (cung) e(x, y) được tương ứng với hai 
biến dau[e], cuoi[e].
– Như vậy, để lưu trữ đồ thị, ta cần 2m đơn vị bộ nhớ.
– Nhược điểm: để nhận biết những cạnh nào kề với cạnh nào 
chúng ta cần m phép so sánh trong khi duyệt qua tất cả m cạnh 
(cung) của đồ thị.
– Nếu là đồ 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.
15
Biểu diễn đồ thị vô hướng bằng danh sách cạnh
• Chỉ cần liệt kê các cạnh (u,v) mà không cần liệt kê cạnh (v,u).
• Nên liệt kê các cạnh theo thứ tự tăng dần của đỉnh đầu mỗi 
cạnh.
• Tính chất danh sách cạnh của đồ thị vô hướng: 
– Đỉnh đầu nhỏ hơn đỉnh cuối mỗi cạnh. 
– Số cạnh có giá trị u thuộc cả vế phải và vế trái của danh sách 
cạnh là bậc của đỉnh u.
16
Biểu diễn đồ thị có hướng bằng danh sách cạnh
• Mỗi cạnh là bộ có tính đến thứ tự các đỉnh.
• Đặc biệt chú ý đến hướng của các cạnh
• Tính chất danh sách cạnh của đồ thị vô hướng: 
– Đỉnh đầu không nhất thiết phải nhỏ hơn đỉnh cuối mỗi cạnh.
– Số cạnh có giá trị u thuộc cả vế phải các cạnh là deg+(u).
– Số cạnh có giá trị u thuộc cả vế trái các cạnh là deg-(u).
17
Biểu diễn đồ thị trọng số bằng danh sách 
cạnh
• Bổ sung thêm một cột là trọng số của mỗi cạnh
18
Ưu & nhược điểm của danh sách 
cạnh
• Ưu điểm của danh sách cạnh: 
– Trong trường hợp đồ thị thưa (m 6n), biểu diễn bằng 
danh sách cạnh tiết kiệm được không gian nhớ; 
– Thuận lợi cho một số thuật toán chỉ quan tâm đến các 
cạnh của đồ thị. 
• Nhược điểm của danh sách cạnh: 
– Khi cần duyệt các đỉnh kề với đỉnh u bắt buộc phải 
duyệt tất cả các cạnh của đồ thị.
• Điều này làm cho thuật toán có chi phí tính toán cao.
19
Khuôn dạng lưu trữ danh sách cạnh
• Dòng đầu tiên ghi lại số N, M tương ứng với số đỉnh và 
số cạnh của đồ thị.
– Hai số được viết cánh nhau một vài khoảng trống; 
• M dòng kế tiếp, mỗi dòng gi lại một cạnh của đồ thị
– Đỉnh đầu và đỉnh cuối mỗi cạnh được viết cách nhau một vài 
khoảng trống.
20
Cấu trúc dữ liệu biểu diễn danh sách cạnh 
(1/4)
• Biểu diễn danh danh sách cạnh của đồ thị bằng mảng:
//Định nghĩa một cạnh của đồ thị 
typedef struct { 
int dau; 
int cuoi; 
} Edge; 
//Danh sách các cạnh được biểu diễn trong mảng G 
Edge G[MAX];
21
Cấu trúc dữ liệu biểu diễn danh 
sách cạnh (2/4)
• Ví dụ:
22
Cấu trúc dữ liệu biểu diễn danh sách cạnh 
(3/4)
//Định nghĩa một cạnh có trọng số của đồ thị 
typedef struct { 
int dau; 
int cuoi; 
int trongso; 
} Edge; 
//Danh sách các cạnh được biểu diễn trong mảng G 
Edge G[MAX];
23
Cấu trúc dữ liệu biểu diễn danh sách cạnh 
(4/4)
• Biểu diễn danh danh sách cạnh của đồ thị bằng danh 
sách liên kết:
typedef struct canh{ //Định nghĩa một cạnh của đồ thị 
int dau; 
int cuoi; 
struct canh *next; 
} *Edge; 
Edge *G; //Các cạnh được biểu diễn bằng danh danh sách liên kết G.
24
Biểu diễn đồ thị bằng danh sách 
kề
Danh sách kề
• Với mỗi đỉnh u của đồ thị chúng ta lưu trữ danh sách các 
đỉnh kề với nó mà ta ký hiệu là Ke(u), nghĩa là
26
Ưu & nhược điểm của danh sách kề
• Ưu điểm của danh sách kề: 
– Dễ dàng duyệt tất cả các đỉnh của một danh sách kề; 
– Dễ dàng duyệt các cạnh của đồ thị trong mỗi danh 
sách kề; 
– Tối ưu về phương pháp biểu diễn. 
• Nhược điểm của danh sách kề: 
– Khó khăn cho người đọc có kỹ năng lập trình yếu.
27
Biểu diễn danh sách kề dựa vào 
mảng
• Mảng được chia thành n đoạn
– Đoạn thứ i trong mảng lưu trữ danh sách kề của đỉnh thứ i V.
– Để biết một đoạn thuộc mảng bắt đầu từ phần tử nào đến phần 
tử nào ta sử dụng một mảng khác dùng để lưu trữ vị trí các phần 
tử bắt đầu và kết thúc của đoạn.
28
VT[6] = {0, 2, 6, 9, 13, 16, 18}
Biểu diễn danh sách kề bằng danh 
sách liên kết
• Với mỗi đỉnh u V, ta biểu diễn mỗi danh sách kề của 
đỉnh bằng một danh sách liên kết List(u).
29
Khuôn dạng lưu trữ danh sách kề
• Dòng đầu tiên ghi lại số đỉnh của đồ thị 
– N dòng kế tiếp ghi lại danh sách kề của đỉnh tương ứng theo 
khuôn dạng: 
• Phần tử đầu tiên là vị trí kết thúc của đoạn, tiếp đến là 
danh sách các đỉnh của danh sách kề 
– Các phần tử được ghi cách nhau một vài khoảng trống
30
Bài tập 1
• Trong một buổi gặp mặt, một số khách 
mời bắt tay với một số khách mời khác. 
Chứng minh rằng tổng số lượt bắt tay của 
tất cả các khách mời là số chẵn.
31
Bài tập 2
• Một đơn đồ thị vô hướng với n đỉnh có 
nhiều nhất là bao nhiêu cạnh?
32
Bài tập 3
Hãy biểu diễn đồ thị vô hướng dưới đây dưới dạng: 
1) Ma trận kề 
2) Danh sách cạnh 
3) Danh sách kề
33
Bài tập 4
Hãy biểu diễn đồ thị có hướng dưới đây dưới dạng: 
1) Ma trận kề 
2) Danh sách cạnh 
3) Danh sách kề
34
Bài tập 5
Hãy biểu diễn đồ thị có hướng dưới đây dưới dạng: 
1) Ma trận kề 
2) Danh sách cạnh 
35