Bài giảng Thiết kế và đánh giá thuật toán - Đồ thị - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Đồ Thị
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Định nghĩa

 Biểu diễn

 Tìm kiếm

 Sắp xếp topo
1
Định Nghĩa
Đồ thị 
 = (, ) bao gồm

 Tập  các đỉnh

 Tập  ⊆  ×  cạnh

 Đồ thị vô hướng

 Cặp cạnh không có thứ tự 
,  = (, 
)

 Đồ thị định hướng

 Cặp cạnh có thứ tự 
,  ≠ , 
Cả hai trường hợp,  ∈ (  )
Nếu 
 liên thông,  ≥  − 1
⟹ log  =  log 
2
Biểu Diễn

 Danh sách liền kề

Mảng 1 chiều  danh sách

Mỗi danh sách cho một đỉnh 
 bao gồm

Các đỉnh  sao cho 
,  ∈ 

 Ma trận liền kề

Mảng 2 chiều  × 

 Đỉnh được đánh số 1, 2,  , 

Giá trị 1 thể hiện có cạnh ,  ∈ 
3
Biểu Diễn – Danh Sách

 Danh sách liền kề

Mảng 1 chiều  danh sách

Mỗi danh sách cho một đỉnh 
 bao gồm

Các đỉnh  sao cho 
,  ∈ 
 1  	 2, 3
 2! 	 	 "3#
 3! 	 	 "#
 4! 	 	 "3#
4
Biểu Diễn – Ma Trận

 Ma trận liền kề

Mảng 2 chiều  × 

 Đỉnh được đánh số 1, 2,  , 

Giá trị 1 thể hiện có cạnh ,  ∈ 
5
Biểu Diễn – So Sánh

 Danh sách liền kề

 Sử dụng khi đồ thị thưa

  nhỏ hơn nhiều so với  

 Xác định danh sách đỉnh đi được từ 

 Ma trận liền kề

 Sử dụng khi đồ thị dầy

  gần bằng  

 Xác định có cạnh 
,  ∈ 

 Sử dụng cho cả đồ thị vô hướng và có hướng
6
Tìm Kiếm

 Xác định cấu trúc của đồ thị

 Thăm tất cả các đỉnh của 

Mỗi đỉnh thăm một lần

 Sử dụng các cạnh trong 

 02 phương pháp

 Theo bề rộng (Breath First Search – BFS)

 Theo bề sâu (Depth First Search – DFS)
7
Tìm Kiếm – BFS

 Từ 
 lần lượt thăm tất cả các  liền kề 
mà  chưa được thăm

 Sau đó, đỉnh nào được thăm trước thì 
các đỉnh kề nó cũng sẽ được thăm trước

 Tiếp tục cho tới khi không thể thăm đỉnh 
nào nữa
8
Tìm Kiếm – BFS – Ví Dụ
1 2 3 4 5 7 8 6 9 10 11 12 13
9
Tìm Kiếm – BFS – Mã Giả
Algorithm BFS(u)
Input: Đỉnh u chưa được thăm
Khởi tạo hàng đợi Q rỗng
Đánh dấu đỉnh u đã được thăm
Q.enqueue(u)
while Q.empty() ≠ TRUE
v  Q.dequeue()
for (mỗi đỉnh w kề v)
if (w chưa được thăm)
Đánh dấu w đã được thăm
Q.enqueue(w)
10
Tìm Kiếm – BFS – Phân Tích

 Thao tác trên hàng đợi: (  )

 Đỉnh thêm/bớt ở hàng đợi 1 lần duy nhất

 Duyệt danh sách liền kề: (  )

 Khi đỉnh bị loại khỏi hàng đợi

Một lần duy nhất

 Độ dài danh sách  

 Khởi tạo: (  )

 Đánh dấu các đỉnh chưa thăm

 Tổng thời gian: (  +  )
11
Tìm Kiếm – BFS – Ứng Dụng

 Xác định có đường đi từ 
 đến  không

 Kiểm tra tính liên thông

 Xác định thành phần liên thông
12
Tìm Kiếm – DFS

 Từ 
 thăm  liền kề 

 Từ  thăm & liền kề 

 Cứ thể tiếp tục khi có thể được

 Khi tới  mà tại  không thăm tiếp được, 
quay lại 
 trước đó, thăm ′ khác của 

 Tiếp tục cho tới khi không thể thăm đỉnh 
nào nữa
13
Tìm Kiếm – DFS – Ví Dụ
1 2 3 5 4 6 7 8 9 10 11 12 13
14
Tìm Kiếm – DFS – Mã Giả
Algorithm DFS(u)
Input: Đỉnh v chưa được thăm
Đánh dấu đỉnh u đã được thăm
for (mỗi đỉnh v kề u)
if (v chưa được thăm)
Đánh dấu v đã được thăm
DFS(v)
15
Tìm Kiếm – DFS – Ứng Dụng

 Phân lớp cung

 Phát hiện chu trình
16
Sắp Xếp Topo

 Nhiều danh quan hệ trên tập đối tượng
có thể biểu diễn bới đồ thị định hướng
không chu trình

 Quan hệ thứ tự bộ phận

 Quan hệ thứ tự thời gian giữa các nhiệm vụ
trong đề án

 Quan hệ thứ tự thời gian giữa các môn học
trong một chương trình học
17
Sắp Xếp Topo – Ví Dụ
18
CTDL
>
Trí tuệ
nhân
tạo
LTHĐT
LTTT
LTNC Toán
cao
cấp
Sắp Xếp Topo

 
 = (, ) là đồ thị định hướng không chu trình

 Sắp xếp các đỉnh đồ thị thành một danh sách

 Sao cho nếu có cung 
,  thì 
 cần đứng
trước  trong danh sách đó
19
d
a
e
c
f
b
(a, c, b, d, e, f)
hoặc
(a, b, d, c, e, f)
Sắp Xếp Topo

 Sắp xếp topo dựa trên DFS

 Thực hiện DFS trên đồ thị

 Khi kết thúc quá trình DFS trên một đỉnh

 thì thêm 
 vào cuối danh sách

 Kết thúc DFS trên toàn đồ thị, đảo ngược
danh sách, được sắp xếp topo
20
Sắp Xếp Topo – Ví Dụ
21
d
a
e
c
f
b
DFS(a)
DFS(c)
DFS(e)
L = (e)
L = (e, c)
DFS(d)
DFS(f)
L = (e, c, f)
L = (e, c, f, d)
L = (e, c, f, d, a)
DFS(b)
L = (e, c, f, d, a, b)
L = (b, a, d, f, c, e)