Giáo trình Toán rời rạc - Bài 17: Tìm kiếm trên đồ thị - Trần Vĩnh Đức
Tìm kiếm trên đồ thị (Version 0.4)
Trần Vĩnh Đức
HUST
Ngày 29 tháng 7 năm 2018
1 / 57
Tài liệu tham khảo
▶
▶
S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,
Algorithms, July 18, 2016.
Chú ý: Nhiều hình vẽ trong tài liệu được lấy tùy tiện mà chưa
xin phép.
2 / 57
Nội dung
Biểu diễn đồ thị
Tìm kiếm theo chiều sâu trên đồ thị vô hướng
Tìm kiếm theo chiều sâu trên đồ thị có hướng
Thành phần liên thông mạnh
Biểu diễn đồ thị dùng Ma trận kề
Nếu đồ thị có n = |V| đỉnh v1, v2, . . . , vn, thì ma trận kề là một
mảng n × n với phần tử (i, j) của nó là
{
1
0
nếu có cạnh từ vi tới vj
ngược lại.
aij =
Ví dụ
v2
1 1 1
v1
A = 0 0 1
0 1 0
v3
4 / 57
Dùng ma trận kề có hiệu quả?
▶
▶
Có thể kiểm tra có cạnh nối giữa cặp đỉnh bất kỳ chỉ cần một
lần truy cập bộ nhớ.
Tuy nhiên, không gian lưu trữ là O(n )
2
5 / 57
Biểu diễn đồ thị dùng danh sách kề
▶
▶
Dùng một mảng Adj gồm |V| danh sách.
Với mỗi đỉnh u ∈ V, phần tử Adj[u] lưu trữ danh sách các
hàng xóm của u. Có nghĩa rằng:
Adj[u] = {v ∈ V | (u, v) ∈ E}.
Ví dụ
1
2
Adj[0] = {0, 1, 2}
Adj[1] = {2}
Adj[2] = {1}
0
6 / 57
Dùng danh sách kề có hiệu quả?
▶
▶
Có thể liệt kê các đỉnh kề với một đỉnh cho trước một cách
hiệu quả.
2
Nó cần không gian lưu trữ là O(|V| + |E|). Ít hơn O(|V| ) rất
nhiều khi đồ thị ít cạnh.
7 / 57
Nội dung
Biểu diễn đồ thị
Tìm kiếm theo chiều sâu trên đồ thị vô hướng
Tìm kiếm theo chiều sâu trên đồ thị có hướng
Thành phần liên thông mạnh
Câu hỏi
Từ một đỉnh của đồ thị ta có thể đi tới những đỉnh nào?
9 / 57
Tìm đường trong mê cung
L
K
F
D
A
C
K
B
E
H
G
B
G
H
F
L
I
J
C
E
J
I
A
D
Hình: Tìm kiếm trên đồ thị cũng giống tìm đường trong mê cung
10 / 57
procedure explore(G, v)
Input: đồ thị G = (V, E); v ∈ V
Output: visited(u)=true với mọi đỉnh u có thể đến
được từ v
visited(v) = true
previsit(v)
for each edge (v, u) ∈ E:
if not visited(u): explore(G, u)
postvisit(v)
11 / 57
Ví dụ: Kết quả chạy explore(G, A)
A
D
A
C
K
B
E
B
D
G
H
G
H
F
L
I
J
F
C
E
I
J
12 / 57
Tìm kiếm theo chiều sâu
procedure dfs(G)
for all v ∈ V:
visited(v) = false
for all v ∈ V :
if not visited(v): explore(G, v)
13 / 57
Ví dụ: Đồ thị và Rừng DFS
1,10
A
11,22
C
23,24
F
(a)
(b)
A
E
I
B
F
J
C
G
K
D
H
L
4,9
5,8
B
12,21
13,20
E
I
D
H
2,3
14,17
L
J
G
6,7
18,19
K
15,16
14 / 57
Bài tập
Xây dựng rừng DFS cho đồ thị sau với các đỉnh lấy theo thứ tự từ
điển. Vẽ cả những cạnh nét đứt.
15 / 57
Rừng DFS và số thành phần liên thông
1,10
11,22
23,24
v
A
B
C
D
E
F
G
H
I
ccnum[v]
A
F
C
1
1
2
2
1
3
2
2
1
1
4,9
5,8
B
12,21
13,20
E
I
D
H
2,3
14,17
L
J
G
6,7
18,19
K
J
15,16
Biến ccnum[v] để xác định thành phần liên thông của đỉnh v.
16 / 57
Tính liên thông trong đồ thị vô hướng
procedure dfs(G)
cc = 0
for all v ∈ V: visited(v) = false
for all v ∈ V:
if not visited(v):
cc = cc + 1
explore(G, v)
procedure explore(G, v)
visited(v) = true
previsit(v)
for each edge (v, u) ∈ E:
if not visited(u): explore(G, u)
postvisit(v)
procedure previsit(v)
ccnum[v] = cc
17 / 57
Bài tập
Hãy cài đặt chương trình tìm số thành phần liên thông của một đồ
thị vô hướng.
18 / 57
previsit và postvisit
▶
▶
▶
Lưu thời gian lần đầu đến đỉnh trong mảng pre
Lưu thời gian lần cuối rời khỏi đỉnh trong mảng post
Để tính hai thông tin này ta dùng một bộ đếm clock, khởi
tạo bằng 1, và được cập nhật như sau:
procedure previsit(v)
pre[v] = clock
clock = clock + 1
procedure postvisit(v)
post[v] = clock
clock = clock + 1
19 / 57
Bài tập
Vẽ rừng DFS với cả số pre và post cho mỗi đỉnh cho đồ thị sau.
20 / 57
Tải về để xem bản đầy đủ
57 trang
13880
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 17: Tìm kiếm trên đồ thị - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_bai_17_tim_kiem_tren_do_thi_tran_vin.pdf
