Download miễn phí Bài giảng Cấu trúc dữ liệu và giải thuật - Đại học bách khoa Hà Nội
Tìm kiếm theo chiều sâu Depth-First Search (DFS)
-DFS là một phép tìm kiếm trên đồthị phổ biến khác
{Vềmặt ý tưởng, tương tựnhưphép duyệt theo
thứtựtrước(thăm nút, rồi thăm các nút con
một cách đệquy)
-DFS có thểchỉ ra một sốthuộc tính của đồthị mà BFS không thể
{Nó có thểcho biết đồthị có chu trình hay không
{Học sâu hơn trong Toán Rời Rạc
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
tập E(G)các cạnh (cung) là các cặp đỉnh.
a b c d
e
i
f g h
j k l
V = { a, b, c, d, e, f, g, h, i, j, k, l }
E = { (a, b), (a, e), (b, e), (b, f), (c, j), (c, g), (c, h), (d, h), (e, j),
(g, k), (g, l), (g, h), (i, j) }
đỉnh
cạnh
12 đỉnh
13 cạnh
Đồ thị định hướng
Trong đồ thị định hướng (digraph), các cạnh là những cặp
có thứ tự. TW 45
U A
1
2 0
AA 49
AA 411
AA 523
A
A
1387
D
L 335
U
A
8
7
7
AA 903
DL 247
NW 35
SFO
ORD
BOS
JFK
LAX DFW
MIA
Ứng dụng của đồ thị
Đồ thị mô tả các mối quan hệ
Mạng Internet
Mạng lưới đường giao thông
Nguyên tử
Mạng lưới xã hội
Bề mặt địa lý (CAD)
Mạch điện
…
JohnYokoRingoGeorgePaulLinda
Sơ đồ cấu trúc điều khiển
Các loại đồ thị khác
Đa đồ thị cho phép có thể có nhiều cạnh giữa 2 đỉnh.
a
b d f
c
Giả đồ thị là một đa đồ thị cho phép vòng lặp (là các cạnh từ một đỉnh
đến chính nó).
1
54
2 3
6
Cạnh và Đỉnh
u
w
v
e
e1
2
bậc(u) = 2
bậc(w) = 1
b
a
d
e
c
đỉnh đích
đỉnh nguồn
bậc vào(b) = 3
bậc ra(b) = 4
u và v gọi là lân cận của nhau hay kề nhau (adjacent)
Đường đi
Một đường đi có độ dài k là một chuỗi các đỉnh v , v , …, v mà
(v , v ) với i = 0, 1, …, k – 1 là cạnh của G.
0 1 k
i i+1
g
a
e
j
n
b
f
k
dc
o
h
l
p
m
q
Không phải đường đi đơn:
a, b, e, f, g, b, g, l
Đường đi đơn:
a, e, k, p, l, q
m, h, d, c, g
(không có đỉnh
lặp lại)
b, c, d không phải đường đi
Chu trình
a
e
j
n
b
f
k
dc
o
g h
l
p
m
q
Một chu trình là một đường đi có đỉnh đầu và đỉnh cuối trùng nhau.
Một chu trình đơn không có đỉnh trùng nhau trừ đỉnh đầu và đỉnh cuối.
k, j, n, k, p, o,k
không phải chu
trình đơn.
Đồ thị con
a
e
j
n
b
f
k
dc
o
g h
l
p
m
q
Một đồ thị con H của G
là một đồ thị;
các cạnh và các đỉnh của nó là tập con của G.
V(H) = {b, d, e, f, g, h, l, p, q} E(H) = {(b, e), (b, g), (e, f), (d, h), (l, p), (l, q)}
Liên thông
G được gọi là liên thông nếu giữa mọi cặp đỉnh của G đều có 1 đường đi..
a
b
d
fe
c
Nếu G là không liên thông, các đồ thị con liên thông lớn nhất được gọi là
các thành phần liên thông của G.
e f ga
cb
dC
C
C
1
3
2
Cây có phải là liên thông?
Có, và | E | = | V | – 1.
Nếu G là liên thông, thì | E | ≥ | V | – 1.
#số cạnh #số đỉnh
Đồ thị có trọng số
A
B
H G E
D
C
F
10 km
7 km
2 km
12 km
8 km
21 km
19 km
5 km
9 km
6 km
VD. Mạng lưới giao thông
2. Biểu diễn đồ thị
z 2 cách biểu diễn đồ thị phổ biến.
1. Ma trận kề (Adjacency Matrix)
Sử dụng một ma trận 2 chiều
2. Danh sách kề (Adjacency List)
Sử dụng một mảng của danh sách móc nối
Ma trận kề
1
0 2
4 3
bool A [n][n];
A[j] =
1 nếu (i, j) ∈ E(G)
0 ngược lại
0 0 1 1 0 1
1 1 0 1 0 0
2 1 1 0 1 1
3 0 0 1 0 1
4 1 0 1 1 0
0 1 2 3 4
Lưu trữ: O(|V| ).2
Thường được sử dụng với đồ thị nhỏ, không hiệu quả với
đồ thị có ít cạnh
Đồ thị không định hướng
Danh sách kề
B
A C
E D
B 2 C 5 E 7
A 2 C 6
A 5 B 6 D 10 E 3
C 10 E 2
A 7 C 3 D 2
Nếu G là định hướng, tổng độ dài của tất cả danh sách kề = | E |.
A
B
C
D
E
Đỉnh Tập các đỉnh kề
Nếu G không định hướng, tổng độ dài là 2 | E |.
Chi phí bộ nhớ: O(|V| + |E|). (Tốn ít bộ nhớ hơn).
2
7
5
6
3 10
2
• Danh sách kề là một mảng A[0..n-1] các danh sách, với n
là số đỉnh của đồ thị.
• Chỉ số của mảng tương ứng với chỉ số của đỉnh
• Mỗi danh sách A lưu trữ các chỉ số của các đỉnh kề với
đỉnh i.
Ví dụ
2
4
3
5
1
7
6
9
8
0 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 1 0 1
2 0 1 0 0 1 0 0 0 1 0
3 0 1 0 0 1 1 0 0 0 0
4 0 0 1 1 0 0 0 0 0 0
5 0 0 0 1 0 0 1 0 0 0
6 0 0 0 0 0 1 0 1 0 0
7 0 1 0 0 0 0 1 0 0 0
8 1 0 1 0 0 0 0 0 0 1
9 0 1 0 0 0 0 0 0 1 0
Ví dụ
2
4
3
5
1
7
6
9
8
0 0
1
2
3
4
5
6
7
8
9
2 3 7 9
8
1 4 8
1 4 5
2 3
3 6
5 7
1 6
0 2 9
1 8
Phân tích độ phức tạp
Thao tác Danh sách kề Ma trận kề
Duyệt cạnh qua v O(bậc(v)) O(|V|)
Kiểm tra u kề với v O(min(bậc(u), bậc(v)) O(1)
Duyệt cạnh ra của v O(bậc ra(v)) O(|V|)
Duyệt cạnh vào của v O(bậc vào(v)) O(|V|)
Lưu trữ O(|V|+|E|) O(|V| )2
Ma trận kề và danh sách kề
z Danh sách kề
{Tiết kiệm bộ nhớ hơn ma trận kề nếu đồ thị có ít cạnh
{Thời gian kiểm tra một cạnh có tồn tại lớn hơn
zMa trận kề
{Luôn luôn mất n2 không gian bộ nhớ
zĐiều này có thể làm lãng phí bộ nhớ khi đồ thị thưa
{Tìm một cạnh có tồn tại hay không trong thời gian hằng số
3. Phép duyệt đồ thị
z Ứng dụng
{Cho một đồ thị và một đỉnh s thuộc đồ thị
{Tìm tất cả đường đi từ s tới các đỉnh khác
z2 thuật toán duyệt đồ thị phổ biến nhất
z Tìm kiếm theo chiều rộng (BFS)
• Tìm đường đi ngắn nhất trong một đồ thị không có trọng
số
z Tìm kiếm theo chiều sau (DFS)
• Bài toán sắp xếp topo
• Tìm các thành phần liên thông mạnh
z Trước tiên ta sẽ xem xét BFS
Tìm kiếm theo chiều rộng
Tìm đường đi ngắn nhất từ đỉnh nguồn s tới tất cả các nút.
Ý tưởng: Tìm tất cả các nút tại khoảng cách 0, rồi tại
khoảng cách 1, rồi đến khoảng cách 2, …
2
4
3
5
1
7
6
9
8
0
Với s là đỉnh 1
Các nút tại khoảng cách 1?
2, 3, 7, 9
1
1
1
1
2
22
2
s
Ví dụ
Các nút tại khoảng cách 2?
8, 6, 5, 4
Các nút tại khoảng cách 3?
0
•Khoảng cách là số cạnh trên đường đi bắt đầu từ s
BFS – Giải thuật
Một hàng đợi Q để lưu trữ các đỉnh đang đợi
được thăm.
Một mảng flag lưu trạng thái các đỉnh đã được thăm.
Tại mỗi bước, một đỉnh sẽ bị xóa khỏi Q và được
đánh dấu là đã thăm.
Mỗi đỉnh có trạng thái “thăm” như sau:
FALSE: đỉnh là chưa được thăm.
TRUE: đỉnh được đưa vào hàng đợi
BSF algorithm
// chưa được thăm
Ví dụ BFS
s
d
b
g
f
e
c
a
Thứ tự thăm:
Q: s
sd
b
g
f
e
a
c
Thứ tự thăm: s
Q: a, c
sd
b
g
f
e
c
a
Các cạnh có nét đứt chỉ ra rằng đỉnh được xét
nhưng đỉnh đã được thăm.
TT thăm: s, a
Q: c, d
TT thăm: s, a, c
Q: d, e, f
sd
b
g
f
e
c
a
TT thăm: s, a, c, d
Q: e, f
TT thăm: s, a, c, d, e
Q: f, b
TT thăm: s, a, c, d, e, f
Q: b, g
Kết thúc
s
d
b
g
f
e
c
a
TT thăm: s, a, c, d, e, f, b
Q: g
TT thăm: s, a, c, d, e, f, b, g
Q:
Cây duyệt theo chiều rộng
s
d
b
g
f
e
c
a
0
1
1
2
2
2
3
3
d(b): đường đi ngắn nhất từ s đến b
BFS chỉ thăm các tập con có thể đến được từ đỉnh ban đầu
Ví dụ
2
4
3
5
1
7
6
9
8
0
Danh sách kề
nguồn
0
1
2
3
4
5
6
7
8
9
Flag (T/F)
F
F
F
F
F
F
F
F
F
F
Q = { }
Khởi tạo ban đầu
(tất cả = F)
Khởi tạo Q rỗng
Ví dụ
2
4
3
5
1
7
6
9
8
0
Danh sách kề
nguồn
0
1
2
3
4
5
6
7
8
9
Flag (T/F)
F
F
T
F
F
F
F
F
F
F
Q = { 2 }
2 đã được thăm
Flag(2) = T.
Đặt đỉnh nguồn 2 vào queue.
Ví dụ
2
4
3
5
1
7
6
9
8
0
Danh sách kề
nguồn
0
1
2
3
4
5
6
7
8
9
Flag (T/F)
F
T
T
F
T
F
F
F
T
F
Q = {2} → { 8, 1, 4 }
Đánh dấu các nút
kề là đã thăm.
Lấy 2 ra khỏi queue.
Đặt tất cả các nút kề chưa được thăm của 2 vào queue
Nút kề
Ví dụ
2
4
3
5
1
7
6
9
8
0
Danh sách kề
nguôn
0
1
2
3
4
5
6
7
8
9
Flag (T/F)
T
T
T
F
T
F
F
F
T
T
Q = { 8, 1, 4 } → { 1, 4, 0, 9 }
Đánh dấu các nút
mới được thăm.
Lấy 8 ra khỏi queue.
-- Đặt tất cả các nút kề chưa được thăm của 8 vào queue.
-- Chú ý là 2 không được đặt vào queue nữa vì nó đã được thăm
Nút kề
Ví dụ
2
4
3
5
1
7
6
9
8
0
Danh sách kề
nguồn
0
1
2
3
4
5
6
7
8
9
Flag (T/F)
T
T
T
T
T
F
F
T
T
...