Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK
HN 1
Đỗ Bích Diệp - Khoa CNTT
Cấutrúcdữ liệuvàGiảithuật
Chương VIII: CấutrúcĐồ thị
ORD
DFW
SFO
LAX
8
0
2
1
7
4
1
8
4
3
12
33
3
3
7
Đỗ Bích Diệp - Khoa CNTT
Chương VIII: Đồ thị
z Nội dung
1. Các khái niệmcơ bản
2. Biểudiễn đồ thị
1. Ma trậnlâncận

34
12
3
4
5
Trong một cung, thứ tự của
các đỉnh là quan trọng
Cung (u,v) khác với cung (v,u)
Trong một cung, thứ tự của
các đỉnh là không quan trọng
Cung (u,v) cũng giống như cung (v,u
)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK
HN 3
Đỗ Bích Diệp - Khoa CNTT
Các khái niệm liên quan
z Bậccủamột đỉnh (Degree): Là số cung kề với đỉnh
– Trong một đồ thị có hướng, một đỉnh có thể có
z Bậc trong (in-degree)
z Bậc ngoài (out-degree)
– Ví dụ:
z Đỉnh 1 có bậc3
z Đỉnh 1 có bậc trong là 1 và bậc ngoài là 2
12
34
Đỗ Bích Diệp - Khoa CNTT
Các khái niệm liên quan
z Đỉnh lân cận (Adjacent vertices)
– Trong đồ thị

trùng nhau
z Độ dài đường đi
– Số cung trên đường đi
z Đồ thị con
12
34
Path : 1, 2, 4, 3, 1, 4
Đỗ Bích Diệp - Khoa CNTT
Các khái niệm liên quan
z Đồ thị liên thông (Connected Graph)
12
3
4
5
12
34
Đồ thị liên thông
12
3
12
3
4
5
Đồ thị không liên thông
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK
HN 5
Đỗ Bích Diệp - Khoa CNTT
Các khái niệm liên quan
z Đồ thị trọng số (Weight Graph)

Đỗ Bích Diệp - Khoa CNTT
Mộtsố tính chấtcủa đồ thị
1. Nếumột đồ thị G có m cung thì tổng bậccủa
các đỉnh trong G sẽ là 2m
2. Nếumột đồ thị có hướng có m cung thì tổng bậc
trong củacácđỉnh , tổng bậc ngoài củacácđỉnh
đềulàm
3. Nếu đồ thị G là đồ thịđơngiản, G có n đỉnh và
m cung thì
1. NếuG làđồ thị vô hướng m ≤ n(n-1)/2
2. NếuG làđồ thị có hướng thì m ≤ n(n-1)
Đỗ Bích Diệp - Khoa CNTT
Biểudiễn đồ thị
– Biểudiễnbằng ma trậnlâncận
z Đánh số các đỉnh trong tậpV từ 1 đếnn
z Ma trậnbiểudiễn đồ thị A (n x n)
– A
ij
= 1 nếu trong G tồntại cung (i,j)
– A
ịj
= 0 nếu trong G không tồntại cung đó
z Với đồ thị vô hướng thì nếuA
ij
= 1 thì A
ji
= 1
z A đượcgọilàma trậnlâncậncủaG
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK

⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
01001
10100
01011
00101
10110
Đỗ Bích Diệp - Khoa CNTT
Biểudiễn đồ thị bằng danh sách lân cận
– Biểudiễnbằng danh sách lân cận
z Mỗi đỉnh trong đồ thị sẽứng vớimột danh sách móc nốichứa
các đỉnh lân cậncủanó
z Mỗi nút trong danh sách có quy cách
– VERTEX chứagiátrị tương ứng vớisố thứ tự của đỉnh lân cận
– LINK chứa con trỏ trỏ tới nút tiếp theo trong danh sách
z Mỗidanhsáchnhư vậycómộtnútđầudanhsách
z Các nút đầunàylàcácphầntử củamột vector V có kích
thướcn. Phầntử V[i] ứng với danh sách lân cậncủanútthứ i
LINKVERTEX
Cấu trúc dữ liệu và Giải thuật

5
2 3 5
1
1
3
1
2
3
5
4
4
V[1]
V[2]
V[3]
V[4]
V[5]
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK
HN 9
Đỗ Bích Diệp - Khoa CNTT
Phép duyệt đồ thị
z Cho một đồ thị G(V,E) và một đỉnh v thuộcV. Duyệt
đồ thị là thămmọi đỉnh liên thông vớiv
– Có 2 phương pháp
z Phương pháp duyệttheochiều sâu (Depth First Search)
z Phương pháp duyệttheochiềurộng ( Breadth First Search)
Đỗ Bích Diệp - Khoa CNTT
Duyệt theo chiều sâu
Algorithm DFS(G, v)
Input đồ thị G và đỉnh bắt đầu duyệt v trong G

E
Cung khám phá
Cung quay lui
A
Đỉnh đãthăm
A
Đỉnh chưathăm
Cung chưathăm
Bắt đầuxuấtpháttừ A
Đỗ Bích Diệp - Khoa CNTT
Duyệt đồ thị theo chiều sâu
DB
A
C
E
DB
A
C
E
DB
A
C
E
D
B
A
C
E
Tấtcả các cung
kề củaD đãduyệt

setLabel(e, BACK)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK
HN 12
Đỗ Bích Diệp - Khoa CNTT
Duyệt đồ thị theo chiềurộng
C
B
A
E
D
Cung khám phá
Cung quay lui
A
Đỉnh đãthăm
A
Đỉnh chưathăm
Cung chưathăm
L
0
L
1
F
CB
A
E
D
L
0
L

F
L
2
CB
A
E
D
L
0
L
1
F
L
2
CB
A
E
D
L
0
L
1
F
L
2
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBK
HN 13
Đỗ Bích Diệp - Khoa CNTT
Duyệt đồ thị theo chiềurộng

F
L
2
Đỗ Bích Diệp - Khoa CNTT
Duyệt đồ thị theo chiều sâu
z Duyệt đồ thị theo chiềurộng trên đồ thị có hướng
A
B
D
C
E