- Trang Chủ
- Toán học
- Bài giảng Toán rời rạc: Tìm kiếm trên đồ thị (Version 0.4) - Trần Vĩnh Đức
Xem mẫu
- 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- 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 nếu có cạnh từ vi tới vj
aij =
0 ngược lại.
Ví dụ
v2
1 1 1
v1
A = 0 0 1
0 1 0
v3
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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(n2 )
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
Adj[0] = {0, 1, 2}
Adj[1] = {2}
0 Adj[2] = {1}
2
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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ả.
▶ Nó cần không gian lưu trữ là O(|V| + |E|). Ít hơn O(|V|2 ) rất
nhiều khi đồ thị ít cạnh.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- EALIZETHATTHEORDERINWHICHEDGES
WHICHVERTICESAPPEARINTHEARRAYOF
-
H
M
T
E
R
E CâutinyG.txt
hỏi
T VTừ một
13
đỉnh của đồ thị ta có
% thể đi tớiGraph
java những tinyG.txt
đỉnh nào?
E 13 vertices, 13 edges
Y 13
0: 6 2 1 5
0 5
T 4 3
1: 0
2: 0
N 0 1
CuuDuongThanCong.com 3: 5 4
first adjacent
https://fb.com/tailieudientucntt 9 / 57
- Tìm đường trong mê cung
Algorithms 83
Figure 3.2 Exploring a graph is rather like navigating a maze.
L
K
D A B E F
H
B
G H C F I J C G
E
J
K L
I A D
Hình: Tìm kiếm trên đồ thị cũng giống tìm đường trong mê cung
3.2 Depth-first search in undirected graphs
3.2.1 Exploring mazes
Depth-first search is a surprisingly versatile linear-time procedure that reveals a
wealth of information about a graph. The most basic question it addresses is,
What
CuuDuongThanCong.com parts of the graph are reachable from a given vertex?
https://fb.com/tailieudientucntt 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)
CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 57
- Ví dụ: Kết quả chạy explore(G, A) A
Chapter 3
Figure 3.2 Exploring
Figure 3.4a graph is rather
The result like navigating
of explore(A) a maze.
on the graph of Figure
L A
K
D A B E F
B
B D
G H C F I J E F G C
E
J
I C H
K L
I A
J
For instance, while B was being visited, the edge B − E was n
3.2 Depth-first
was as search in undirected
yet unknown, graphs
was traversed via a call to explore(E )
form a tree (a connected graph with no cycles) and are therefo
3.2.1 Exploring mazesedges were ignored because they led back to familia
The dotted
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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)
CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 57
- during explore(x) and once during explore(y). The overall time for step 2 is
therefore O(|E |) and so the depth-first search has a running time of O(|V| + |E |),
Ví dụ: Đồ thị và Rừng DFS
linear in the size of its input. This is as efficient as we could possibly hope for, since
it takes this long even just to read the adjacency list.
Figure 3.6 (a) A 12-node graph. (b) DFS search forest.
1,10 11,22 23,24
(a) (b) A C F
A B C D
B E 4,9 12,21 D
2,3
E F G H
I 5,8 13,20 H
I J K L J 14,17 G L
6,7 18,19
K
15,16
Figure 3.6 shows the outcome of depth-first search on a 12-node graph, once again
breaking ties alphabetically (ignore the pairs of numbers for the time being). The
outer loop of DFS calls explore three times, on A, C , and finally F . As a result,
there are three trees, each rooted at one of these starting points. Together they
constitute a forest.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 / 57
- Rừng
. (b) DFSDFS vàforest.
search số thành phần liên thông
1,10 11,22 23,24
(b) v ccnum[v]
A C F
A 1
B 1
B E 4,9 12,21 D C 2
2,3
D 2
I 5,8 13,20 H E 1
F 3
J 14,17 G L
G 2
6,7 18,19
H 2
I 1
K
J 1
15,16
Biến ccnum[v] để xác định thành phần liên thông của đỉnh v.
depth-first search on a 12-node graph, once again
re the pairs of numbers for the time being). The
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 57
- Bài tập
Vẽ rừng DFS với cả số pre và post cho mỗi đỉnh cho đồ thị sau.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 57
nguon tai.lieu . vn
