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
(cid:1) Định nghĩa (cid:1) Biểu diễn (cid:1) Tìm kiếm (cid:1) Sắp xếp topo
1
Nội Dung
Đồ thị (cid:1) = ((cid:4), (cid:6)) bao gồm (cid:1) Tập (cid:4) các đỉnh (cid:1) Tập (cid:6) ⊆ (cid:4) × (cid:4) cạnh (cid:1) Đồ thị vô hướng
(cid:1) Cặp cạnh không có thứ tự (cid:10), (cid:11) = ((cid:11), (cid:10))
(cid:1) Đồ thị định hướng
(cid:1) Cặp cạnh có thứ tự (cid:10), (cid:11) ≠ (cid:11), (cid:10) Cả hai trường hợp, (cid:6) ∈ (cid:14)( (cid:4) (cid:15)) Nếu (cid:1) liên thông, (cid:6) ≥ (cid:4) − 1
⟹ log (cid:6) = (cid:23) log (cid:4)
2
Định Nghĩa
(cid:1) Danh sách liền kề
(cid:1) Mảng 1 chiều (cid:4) danh sách (cid:1) Mỗi danh sách cho một đỉnh (cid:10) bao gồm
(cid:1)Các đỉnh (cid:11) sao cho (cid:10), (cid:11) ∈ (cid:6)
(cid:1) Ma trận liền kề
(cid:1) Mảng 2 chiều (cid:4) × (cid:4) (cid:1) Đỉnh được đánh số 1, 2, … , (cid:4)
(cid:1)Giá trị 1 thể hiện có cạnh (cid:26), (cid:27) ∈ (cid:6)
3
Biểu Diễn
(cid:1) Danh sách liền kề
(cid:1) Mảng 1 chiều (cid:4) danh sách (cid:1) Mỗi danh sách cho một đỉnh (cid:10) bao gồm
(cid:1)Các đỉnh (cid:11) sao cho (cid:10), (cid:11) ∈ (cid:6)
Biểu Diễn – Danh Sách
4
(cid:28)(cid:29)(cid:27) 1 (cid:2) 2, 3 (cid:28)(cid:29)(cid:27) 2! (cid:2) "3# (cid:28)(cid:29)(cid:27) 3! (cid:2) "# (cid:28)(cid:29)(cid:27) 4! (cid:2) "3#
(cid:1) Ma trận liền kề
(cid:1) Mảng 2 chiều (cid:4) × (cid:4) (cid:1) Đỉnh được đánh số 1, 2, … , (cid:4)
(cid:1)Giá trị 1 thể hiện có cạnh (cid:26), (cid:27) ∈ (cid:6)
5
Biểu Diễn – Ma Trận
(cid:1) Danh sách liền kề
(cid:1) Sử dụng khi đồ thị thưa (cid:1) (cid:6) nhỏ hơn nhiều so với (cid:4) (cid:15) (cid:1) Xác định danh sách đỉnh đi được từ (cid:10)
(cid:1) Ma trận liền kề
(cid:1) Sử dụng khi đồ thị dầy (cid:1) (cid:6) gần bằng (cid:4) (cid:15) (cid:1) Xác định có cạnh (cid:10), (cid:11) ∈ (cid:6)
(cid:1) Sử dụng cho cả đồ thị vô hướng và có hướng
6
Biểu Diễn – So Sánh
(cid:1) Xác định cấu trúc của đồ thị (cid:1) Thăm tất cả các đỉnh của (cid:4) (cid:1) Mỗi đỉnh thăm một lần (cid:1) Sử dụng các cạnh trong (cid:6)
(cid:1) 02 phương pháp
(cid:1) Theo bề rộng (Breath First Search – BFS) (cid:1) Theo bề sâu (Depth First Search – DFS)
7
Tìm Kiếm
(cid:1) Từ (cid:10) lần lượt thăm tất cả các (cid:11) liền kề (cid:10)
Tìm Kiếm – BFS
(cid:1) Sau đó, đỉnh nào được thăm trước thì
mà (cid:11) chưa được thăm
các đỉnh kề nó cũng sẽ được thăm trước (cid:1) Tiếp tục cho tới khi không thể thăm đỉnh
8
nào nữa
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 (cid:2)(cid:2)(cid:2)(cid:2) 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
(cid:1) Thao tác trên hàng đợi: (cid:14)( (cid:4) )
(cid:1) Đỉnh thêm/bớt ở hàng đợi 1 lần duy nhất
(cid:1) Duyệt danh sách liền kề: (cid:14)( (cid:6) ) (cid:1) Khi đỉnh bị loại khỏi hàng đợi (cid:1) Một lần duy nhất (cid:1) Độ dài danh sách (cid:23) (cid:6)
(cid:1) Khởi tạo: (cid:14)( (cid:4) )
(cid:1) Đánh dấu các đỉnh chưa thăm
(cid:1) Tổng thời gian: (cid:14)( (cid:4) + (cid:6) )
11
Tìm Kiếm – BFS – Phân Tích
(cid:1) Xác định có đường đi từ (cid:10) đến (cid:11) không (cid:1) Kiểm tra tính liên thông (cid:1) Xác định thành phần liên thông
12
Tìm Kiếm – BFS – Ứng Dụng
(cid:1) Từ (cid:10) thăm (cid:11) liền kề (cid:10) (cid:1) Từ (cid:11) thăm & liền kề (cid:11) (cid:1) Cứ thể tiếp tục khi có thể được (cid:1) Khi tới (cid:11) mà tại (cid:11) không thăm tiếp được, quay lại (cid:10) trước đó, thăm (cid:11)′ khác của (cid:10) (cid:1) Tiếp tục cho tới khi không thể thăm đỉnh
Tìm Kiếm – DFS
13
nào nữa
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
(cid:1) Phân lớp cung (cid:1) Phát hiện chu trình
16
Tìm Kiếm – DFS – Ứng Dụng
(cid:1) 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 (cid:1) Quan hệ thứ tự bộ phận (cid:1) Quan hệ thứ tự thời gian giữa các nhiệm vụ
trong đề án
(cid:1) 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
Sắp Xếp Topo – Ví Dụ
LTNC
Toán cao cấp
LTHĐT
CTDL >
LTTT
Trí tuệ nhân tạo
18
(cid:1) (cid:1) = ((cid:4), (cid:6)) là đồ thị định hướng không chu trình (cid:1) Sắp xếp các đỉnh đồ thị thành một danh sách (cid:1) Sao cho nếu có cung (cid:10), (cid:11) thì (cid:10) cần đứng
trước (cid:11) trong danh sách đó
Sắp Xếp Topo
a
b
c
d
(a, c, b, d, e, f) hoặc (a, b, d, c, e, f) …
e
f
19
(cid:1) Sắp xếp topo dựa trên DFS (cid:1) Thực hiện DFS trên đồ thị (cid:1) Khi kết thúc quá trình DFS trên một đỉnh
Sắp Xếp Topo
(cid:1) Kết thúc DFS trên toàn đồ thị, đảo ngược
(cid:10) thì thêm (cid:10) vào cuối danh sách
20
danh sách, được sắp xếp topo
DFS(a)
DFS(c)
Sắp Xếp Topo – Ví Dụ
a
b
DFS(e)
L = (e) L = (e, c)
DFS(d)
DFS(f)
c
d
L = (e, c, f) L = (e, c, f, d) L = (e, c, f, d, a)
DFS(b)
e
f
L = (e, c, f, d, a, b)
L = (b, a, d, f, c, e)
21
