CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
Chương này giới thiệu các phương pháp để biểu diễn một đồ thị và để tìm
kiếm một đồ thị. Việc tìm kiếm một đồ thị có nghĩa là chỉ ra các cạnh một cách có
hệ thống của đồ thị để thăm các đỉnh của đồ thị. Một thuật toán tìm kiếm đồ thị có
thể khám phá nhiều về cấu trúc của đồ thị. Một số thuật toán bắt đầu bởi việc tìm
kiếm dữ liệu vào cho đồ thị của chúng để tìm được cấu trúc thông tin đó. Mặt khác
các thuật toán đồ thị được tổ chức để xây dựng đơn giản các thuật toán tìm kiếm đồ
thị cơ bản. Kỹ thuật để tìm kiếm một đồ thị là điểm cốt lõi trong lĩnh vực của các
thuật toán đồ thị.
Mục 22.1 thảo luận hai cách biểu diễn thuật toán thông thường của các đồ thị: như
các danh sách kề và các ma trận kề. Mục 22.2 giới thiệu một thuật toán tìm kiếm
đồ thị đơn giản gọi là tìm kiếm theo chiều rộng và chỉ ra cách khởi tạo một cây tìm
kiếm theo chiều rộng là như thế nào. Mục 22.3 giới thiệu tìm kiếm theo chiều sâu
và cạnh cấp một số kết quả chuẩn về thứ tự thăm các đỉnh trong tìm kiếm chiều
sâu. Mục 22.4 cung cấp cho chúng ta ứng dụng thực đầu tiên của tìm kiếm theo
chiều sâu: sắp xếp tôpô cho một đồ thị vô hướng có chu trình. Một ứng dụng thứ
hai của tìm kiếm theo chiều sâu là việc tìm các thành phần liên thông mạnh của
một đồ thị vô hướng, được trình bày trong Mục 22.5.
22.1 Biểu diễn đồ thị
Đó là 2 phương pháp để biểu diễn một đồ thị G = (V,E): biểu diễn bằng
danh sách lân cận (kề) hoặc bằng ma trận lân cận (kề). Cả hai phương pháp là ứng
dụng của đồ thị vô hướng và đồ thị vô hướng. Sự biểu diễn bằng ma trận kề là luôn
luôn được ưu tiên, bởi vì nó cung cấp một phương pháp chắc chắn để mô tả đồ thị
không đầy đủ - đó là |E| ít hơn |V|
2
.
Hầu hết các thuật toán biểu diễn đồ thị trong sách này cho rằng dữ liệu
vào của đồ thị được biểu diễn trong danh sách kề. Sự biểu diễn một danh sách kề
có thể được ưu tiên tuy nhiên khi đồ thị là đầy đủ - |E| là đúng |V|
2
Các danh sách kề có thể dễ dàng thích hợp để biểu diễn các đồ thị có trọng
số, nghĩa là, các đồ thị ứng với mỗi cạnh có gắn một trọng số, đặc trưng bởi một
hàm trọng số w: E → R. Ví dụ, cho G = (V,E) là một đồ thị có trọng số với hàm
trọng số w. Trọng số w(u,v) của cạnh (u,v) ∈ E được lưu trữ đơn giản với đỉnh v
trong danh sách kề của u. Sự biểu diễn danh sách kề là khá mạnh mà nó có thể
được sửa đổi để hỗ trợ nhiều phương án cho các đồ thị khác.
Một khả năng bất lợi của sự biểu diễn danh sách kề là không có phương
pháp nào nhanh hơn để xác định nếu một cạnh đã cho (u,v) có trong đồ thị hơn tìm
kiếm v trong danh sách kề Adj[u]. Điểm bất lợi đó có thể được khắc phục bởi một
sự biểu diễn ma trận kề của đồ thị, ở tại đó chi phí của sử dụng gần với bộ nhớ
hơn. (Quan sát bài tập 22.1-8 cho những đề nghị của các biến đổi trên những danh
sách kề mà cho phép tìm kiếm cạnh nhanh hơn).
Để biểu diễn ma trận kề của một đồ thị G = (V,E), chúng ta cho các đỉnh
được đánh số 1, 2, , |V| trong một số kiểu tùy ý. Vì vậy biểu diễn ma trận kề của
một đồ thị G bao gồm một |V| x |V| ma trận A = (a
ij
) trong đó
ij
1
0
a
=
Hình 22.1 (c) và 22.2 (c) lần lượt là các ma trận kề của đồ thị vô hướng và
có hướng trong hình 22.1 (a) và 22.2 (a). Ma trận kề của một đồ thị yêu cầu Ө(V
2
)
bộ nhớ, độc lập với số cạnh trong đồ thị.
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
cách đơn giản như danh sách trong dòng u và cột v của ma trận kề. Nếu một cạnh
không tồn tại, một giá trị NIL có thể được lưu trữ như ma trận danh sách tương
ứng của nó, mặc dù đối với một số bài toán là thuận tiện để sử dụng một giá trị là 0
hoặc ∞.
Mặc dù biểu diễn danh sách kề là lân cận ít hiệu quả như biểu diễn ma trận
kề, sự đơn giản của một ma trận kề có thể khiến cho nó thích hợp khi các đồ thị
nhỏ vừa phải. Hơn nữa, nếu đồ thị là không có trọng số, có một thuận lợi trong
việc lưu trữ để biểu diễn ma trận kề. Ngoài ra việc sử dụng một từ của bộ nhớ máy
tính cho mỗi ma trận danh sách, ma trận kề chỉ dùng một bit cho mỗi danh sách.
BÀI TẬP
22.1-1
Cho một biểu diễn danh sách kề của một đồ thị vô hướng, phải mất bao lâu
để tính toán bậc ra của mỗi đỉnh? Phải mất bao lâu để tính toán bậc vào cho mỗi
đỉnh?
22.1-2
Cho một biểu diễn danh sách kề để một cây nhị phân đầy đủ trên 7 đỉnh.
Cho một biểu diễn ma trận kề tương đương. Cho các cạnh được đánh số từ 1 đến 7
như trong một đống nhị phân.
22.1-3
Chuyển vị của một đồ thị vô hướng G = (V , E) là đồ thị G
T
= (V , E
T
),
trong đó E
T
= { (v,u) ∈ V x V: (u,v) ∈ E}. Vì vậy, G
T
là G với tất cả các cạnh đối
22.1-6.
Khi một biểu diễn ma trận kề được sử dụng, hầu hết các thuật toán đồ thị
yêu cầu thời gian Ω (V
2
) nhưng có một vài trường hợp ngoại lệ. Chỉ ra rằng việc
xác định bất cứ đồ thị vô hướng G chứa một điểm tập trung (universal sink) - một
đỉnh với bậc vào |V| - 1 và bậc ra 0 có thể được xác định trong thời gian O (V),
được cho bởi ma trận kề của G.
22.1-7.
Ma trận tác động (incident matrix) của một đồ thị vô hướng G = (V,E) là
một |V| x |E|, ma trận B = (b
i j
) trong đó
ij
1
1
0
b
−
=
Mô tả như thế nào danh sách của ma trận sản phẩm B biểu diễn B
T
, trong
đó B
T
hạn giữa các đỉnh được tìm ra và các đỉnh không được tìm ra một cách đồng bộ
trong chiều rộng của giới hạn tìm kiếm. Cụ thể là, giải thuật tìm ra tất cả các đỉnh
có khoảng cách từ s là k trước khi tìm ra bất kỳ đỉnh nào có khoảng cách từ s là
k+1.
Để lưu lại các dấu vết tìm kiếm, giải thuật tô màu trắng, xám hay đen cho
từng đỉnh. Tất cả các đỉnh ban đầu là trắng, sau đó có thể là xám rồi thì thành màu
đen. Trong quá trình tìm kiếm, nếu một đỉnh được gọi là được tìm thấy ở lần đầu
tiên nếu như lần tìm thấy đó nó không phải tô màu trắng. Do đó, các đỉnh có màu
xám và màu đen là những đỉnh được tìm thấy nhưng giải thuật phân biệt giữa
chúng để bảo đảm rằng việc tìm kếm được tiến hành là theo cách tìm kiếm rộng.
Nếu (u,v)
∈
E và đỉnh u có màu đen, thì đỉnh v có màu hoặc là xám hoặc là đen.
Có nghĩa là tất cả các đỉnh liền kề với các đỉnh màu đen đều đã được tìm ra. Các
đỉnh màu xám có thể có thể có các đỉnh kề màu trắng, các đỉnh màu trắng này là
giới hạn giữa các đỉnh tìm ra và các đỉnh không tìm ra.
Giải thuật tìm kiếm rộng xây dựng một cây tìm kiếm theo chiều rộng, ban
đầu chỉ chứa gốc là đỉnh s. Bất cứ khi nào một đỉnh v màu trắng được tìm thấy
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 6
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
trong khi đang tìm một danh sách các đỉnh kề của đỉnh u đã tìm ra tước đó, thì đỉnh
u và cạnh (u,v) được thêm vào cây tìm kiếm. Chúng ta gọi đỉnh u là bố của đỉnh v
trong cây tìm kiếm. Bởi vì chỉ có một đỉnh duy nhất được tìm ra nên nó cũng có
một đỉnh cha duy nhất. Các mối quan hệ ông bà và con cháu trong cây tìm kiếm
theo chiều rộng được định nghĩa liên quan đến đỉnh gốc s như thường lệ: nếu đỉnh
u ở trên đường dẫn trong cây tìm kiếm từ đỉnh s đến đỉnh v thì u là tổ tiên của v và
v là con cháu của u.
Chương trình con tìm kiếm theo chiều rộng (BFS) dưới đây giả định rằng
đồ thị nhập vào G=(V,E) là một danh sách các đỉnh liền kề. Nó có các cấu trúc dữ
liệu thêm vào cho từng đỉnh trong đồ thị. Màu của từng đỉnh u
6 d[s]
←
0
7
π
[s]
←
Nil
8 Q
←
φ
9 ENQUEUE (Q,s)
10 While Q
≠
φ
11 do u
←
DEQUEUE (Q)
12 for each v
∈
Adj[u]
13 do if color[v] = WHITE
14 then color[v]
←
GRAY
15 d[v]
←
d[u]+1
Vòng lặp While trong các dòng 10-18 sẽ được thực hiện miễn là các đỉnh
màu xám đang còn, các đỉnh màu xám mà có danh sách các đỉnh kề nó chưa được
xem xét hết đầy đủ. Vòng While này được thực hiện nhờ một điều kiện bất biến
sau:
Ở dòng 10, biến Q bao gồm một tập các đỉnh có màu xám.
Mặc dù, chúng tôi không dùng vòng lặp bất biến này để chứng minh tính đúng
đắn, nhưng thật dễ để nhận ra rằng nó ưu tiên vòng lặp đầu tiên và rằng mỗi lần lặp
lại của vòng lặp duy trì bất biến. Ưu tiên trong vòng lặp đầu tiên, chỉ với các đỉnh
có màu xám, và chỉ với các đỉnh có trong Q, là đỉnh s. Dòng 11 đưa đỉnh u có màu
xám vào ngay đầu danh sách Q và rồi lấy đỉnh u ra khỏi Q liền sau đó. Vòng lặp từ
dòng 12-17 duyệt từng đỉnh v trong danh sách các đỉnh liền kề của đỉnh u. Nếu v
có màu trắng thì nó sẽ chưa được tìm ra và thuật toán sẽ tìm ra nó khi thực hiện các
dòng từ 14 đến 17. Đỉnh v lần đầu được tô màu xám và khoảng cách d[v] được gán
bằng d[u]+1. Sau đó đỉnh u được lưu lại như là đỉnh cha của v. Cuối cùng đỉnh v
được đưa vào cuối của danh sách Q. Khi tất cả các đỉnh trong danh sách các đỉnh
kề của đỉnh u được duyệt hết thì u được tô màu đen theo như dòng 18. Biến vòng
lặp vẫn được duy trì bởi vì bất cứ khi nào một đỉnh được tô màu xám (theo dòng
14) thì nó cũng được đưa vào danh sách Q (theo dòng 17) và bất cứ khi nào một
đỉnh được lấy ra khỏi danh sách Q ( theo dòng 11) thì nó sẽ được tô màu đen (theo
dòng 18).
Các kết quả thu được của giải thuật BFS phụ thuộc vào trật tự mà theo đó,
các đỉnh kề của một đỉnh cho trước đã được xét đến theo dòng 12: cây tìm kiếm
theo chiều sâu có thể thay đổi khác nhau nhưng khoảng các d của đường đi ngắn
nhất được tính bởi giải thuật sẽ không thay đổi. (Xem thêm bài tập 22.2-4).
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 10
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
a.1) Phân tích:
Trước khi chứng minh nhiều đặc tính khác nhau của giải thuật tìm kiếm theo
chiều rộng thì chúng ta hãy xem xét việc dễ dàng hơn là tính toán thời gian chạy
khi đồ thị nhập vào là G = (V,E). Chúng ta sẽ dùng đến các phân tích tổng hợp như
Cho đồ thị G=(V,E) là đồ thị có hướng hoặc vô hướng, và đỉnh s
∈
V bất kỳ,
Với bất kỳ cạnh (u,v)
∈
E ta đều có:
δ
(s,v)<=
δ
(s,u)+1 (1)
Chứng minh bổ đề 22.1:
Nếu từ s đến được u thì s đến được v (vì (u,v)
∈
E). Trong trường hợp này,
đường đi ngắn nhất cần tìm là đường đi ngắn nhất từ s đến u, rồi từ u đi thẳng đến
v theo cạnh (u,v) suy ra bất đẳng thức đã cho đúng. Nếu từ s không thể đến được u
thì
δ
(s,u) =
∞
và suy ra bất đẳng đã cho đúng.
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 11
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
Chúng ta muốn chỉ ra rằng: giải thuật BFS có thể xác định được d[v]=
δ
(s,v)
với mỗi đỉnh v
∈
V. Trước hết chúng ta chỉ ra được d[v] bao
δ
V-{s}
Trong bước quy nạp, duyệt một đỉnh v màu trắng mà được tìm ra trong quá
trình tìm kiếm từ đỉnh u. Từ giả thiết quy nạp ta có: d[u] >=
δ
(s,u)
Từ việc thực hiện câu lệnh gán ở dòng 15 và từ bổ đề 22.1, chúng ta có được:
d[v]=(d[u]+1)>= (
δ
(s,u) +1)>=
δ
(s,v)
Sau đó đỉnh v được đưa vào danh sách Q, và đỉnh v này sẽ không bao giờ được
đưa vào danh sách Q nữa bởi vì nó cũng được tô màu xám và mệnh đề Then từ
dòng 14 đến dòng 17 sẽ chỉ được thực hiện đối với các đỉnh có màu trắng. Do đó,
giá trị của d[v] sẽ không thay đổi nữa và giả thiết quy nạp vẫn được duy trì.
Để chứng minh được rằng d[v]=
δ
(s,v), trước hết chúng ta phải chỉ rõ chính xác
hơn danh sách Q hoạt động như thế nào trong suốt quá trình thực hiện giải thuật
BFS. Bổ đề tiếp theo sẽ chỉ ra rằng sẽ có hai giá trị d phân biệt trong danh sách Q.
d) Bổ đề 22.3:
Giả sử rằng, trong suốt quá trình thực hiện BFS với đồ thị G=(V,E), Q chứa các
đỉnh (v
1
, v
2
, . . . ,v
r
) trong đó v
1
]+1<= d[v
2
]+1
và các bất đẳng thức còn lại thì không bị ảnh hưởng. Vì vậy, theo sau v
2
cũng
giống như ban đầu.
Việc đưa một đỉnh vào danh sách thì cần phải duyệt chương trình kỹ hơn. Khi
chúng ta đưa một đỉnh v theo dòng 17 trong giải thuật BFS vào danh sách Q thì
đỉnh v đó trở thành v
r+1
là đỉnh thứ r+1 trong Q. Lúc này, chúng ta đã xoá đỉnh u
(bởi vì danh sách các đỉnh kề của u đã được duyệt) ra khỏi danh sách Q, và từ giả
thiết quy nạp ta có đỉnh v
1
mới thoã : d[v
1
]>=d[u]
Do đó, d[v
r+1
]=d[v]=(d[u]+1)<=d[v
1
]+1
Cũng từ giả thiết quy nạp, ta có:
d[v
r
]<=d[u]+1
và do đó d[v
r
]<=d[u]+1=d[v]=d[v
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 13
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
Cho đồ thị G=(V,E) là đồ thị có hướng hoặc vô hướng, giả sử rằng BFS được
chạy với G và s
∈
V. Ta có:
* BFS tìm ra mọi đỉnh v
∈
V mà từ đỉnh s có thể đến được thoã: d[v]=
δ
(s,v).
* Ngoài ra, với bất kỳ đỉnh v
≠
s nào thì một trong những đường đi ngắn nhất từ
s đến v đó là đường đi ngắn nhất từ s đến
π
[v] (đỉnh cha của v) rồi đi theo cạnh (
π
[v],v)
Chứng minh định lý:
Giả sử rằng (để tìm ra mâu thuẫn): có vài đỉnh mà có giá trị d không là giá trị
nhỏ nhất theo đường đi ngắn nhất. Xét đỉnh v là đỉnh có khoảng cách
δ
(s,v) =min
mà thỏa điều giả sử trên (có giá trị d không là giá trị nhỏ nhất): rõ ràng v
≠
s
Theo bổ đề 22.2: d[v] >=
δ
(s,v)
(22.1) ở trên.
TH1: nếu v có màu trắng thì theo dòng 15 ta có d[v]=d[u]+1: mâu thuẫn với
(22.1).
TH2: nếu v có màu đen thì theo hệ quả 22.4, khi v đã được xoá khỏi danh sách
Q ta có : d[v]<=d[u]: mâu thuẫn với (22.1)
TH3: nếu v có màu xám có nghĩa là v được tô màu xám khi một đỉnh w nào đó
đứng ngay trước v và đứng sau u, được xoá khỏi danh sách Q. Ta có
d[v]=d[w]+1
Mặt khác theo hệ quả 22.4 thì d[w]<=d[u]
Suy ra: d[v]<=d[u]+1: mâu thuẫn với (22.1)
Vậy, d[v] =
δ
(s,v) với mọi v
∈
V
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 14
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
Chúng ta phải tìm ra được tất cả các đỉnh mà từ s có thể đến được, bởi vì nếu
mà không tìm ra thì thì các giá trị của d phải là không xác định.
Trong phần kết luận của bài toán chúng ta rút ra được:
* nếu
π
[v]=u thì d[v]=d[u]+1
* Chúng ta có thể tìm ra đường đi ngắn nhất bằng cách tìm đường đi ngắn nhất
từ s đến
π
[v] (đỉnh cha của đỉnh v), rồi đi thẳng qua cạnh (
π
[v],v)
g) Cây tìm kiếm theo chiều rộng:
[v],v): v
∈
V-{s}}
Đồ thị
π
G
chứa các đỉnh đứng trước s là cây tìm kiếm theo chiều rộng nếu
π
V
gồm tất cả các đỉnh mà đỉnh s có thể đến được và với mọi đỉnh v
∈
π
V
, thì có một
đường đơn duy nhất từ s đến v trong đồ thị
π
G
đó cũng chính là đường đi ngắn nhất
từ s đến v trong G. Một cây tìm kiếm theo chiều rộng thật sự là một cây bởi vì nó
được kết nối và thỏa:
1−=
ππ
VE
(xem thêm Định lý B.2). Còn các cạnh trong
π
E
được gọi là các nhánh cây.
Sau khi giải thuật BFS thực hiện từ đỉnh s trên G, thì bổ đề sau chỉ rõ rằng đồ
thị con chứa các đỉnh đứng trước đỉnh s là một cây tìm kiếm.
π
G
là một cây nên nó sẽ chứa một đường đi duy nhất đi
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 15
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
từ s đến mỗi đỉnh trong
π
V
. Bằng cách áp dụng định lý 22.5, chúng sẽ rút ra được
mỗi đường đi trong sẽ là đường đi ngắn nhất
π
G
Thủ tục sau đây sẽ in ra các đỉnh trên đường đi ngắn nhất từ s đến v, giả sử rằng
BFS đã được chạy và tìm ra cây chứa đường đi ngắn nhất.
PRINT-PATH(G,s,v)
1. if v=s
2. then print s
3. else if
π
[v]=Nil
4. then print “no path from” s “to” v “exit”
5. else PRINT-PATH(G, s,
π
[v])
6. print v
Thủ tục này tuyến tính theo thời gian, phụ thuộc vào số lượng các đỉnh tìm
được trong đường đi được in ra, vì rằng lời gọi đệ quy được dùng để tìm đường đi
ngắn hơn cho mỗi đỉnh.
Bài tập:
22.2-1: Tìm kết quả của d và
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
một bộ các cạnh
π
E
khi chạy giải thuật BFS trên đồ thị G, cho dù là các đỉnh được
sắp xếp như thế nào trong danh sách các đỉnh liền kề.
22.2-6: Có hai loại người đô vật chuyên nghiệp: “người vật hay” và “người vật
dở”. Giữa bất kỳ một cặp đô vật chuyên nghiệp nào có thể có hoặc không có trận
đấu. Giả sử rằng chúng ta có n đô vật chuyên nghiệp một danh sách các cặp đấu.
Hãy viết giải thuật có độ phức tạp O(n+r) xác định xem có thể chỉ ra các cặp đấu
đấu giữa một “người vật hay” với một “người vật dở” không và in ra kết quả danh
sách đó.
22.2-7: Kích thước của một cây T được xác định bởi
),(max
,
vu
Vvu
δ
∈
Chính là giá trị lớn nhất trong tất cả các khoảng cách của đường đi nhỏ nhất
trong cây tìm kiếm theo chiều rộng. Hãy viết một giải thuật để tính kích thước của
một cây, xác định độ phức tạp của giải thuật.
22.2-8: Cho đồ thị vô hướng và liên thông G=(V,E). Hãy viết một giải thuật có
độ phức tạp là O(V+E) để tìm đường đi trong đồ thị G qua từng cạnh trong E chỉ
một lần theo mỗi hướng.
22.3. Tìm kiếm theo chiều sâu (DFS):
Đi theo chiến lược tìm kiếm theo chiều sâu là, như tên của nó ngụ ý để có
thể tìm kiếm “sâu hơn” trong đồ thị bất cứ khi nào. Trong tìm kiếm theo chiều sâu,
các cạnh được thăm ngoài đỉnh mới tìm thấy nhất v vẫn không thăm những cạnh
=V và π[v] ≠ nil}.
Đồ thị con ở trước của tìm kiếm theo chiều sâu tạo 1 rừng tìm kiếm theo chiều
sâu thành lập một vài cây tìm kiếm chiều sâu. Các cạnh trong E
π
được gọi là các
cạnh cây.
Vì trong tìm kiếm theo chiều rộng, các đỉnh được tô màu trong suốt quá
trình tìm kiếm để chỉ trạng thái của nó. Mỗi đỉnh đầu tiên màu trắng, bị tô xám khi
nó được tìm thấy trong quá trình tìm kiếm, và bị tô đen khi kết thúc,danh sách đỉnh
liền kề với nó được kiểm tra đầy đủ. Kỹ thuật này đảm bảo ràng mỗi đỉnh kết thúc
trên chính xác một cây tìm kiếm chiều sâu, vì thế những cây này tách riêng.
Bên cạnh khởi tạo một rừng tìm kiếm chiều sâu, tìm kiếm theo chiều sâu
cũng gắn nhãn thời gian mỗi đỉnh. Mỗi đỉnh v có 2 nhãn thời gian: gắn nhãn đầu
tiên d[v] khi đỉnh v được tìm thấy đầu tiên ( và tô màu xám ), và gắn nhãn thứ 2
khi quá trình tìm kiếm kết thúc việc kiểm tra danh sách đỉnh liền kề v ( đỉnh v được
tô đen). Những nhãn thời gian này được sử dụng trong nhiều thuật toán đồ thị và
thường hữu ích trong lý do về cách hoạt động của tìm kiếm theo chiều sâu.
Thủ tục DFS ở dưới chỉ ra nó tìm thấy đỉnh u trong biến d[u], và khi nó kết
thúc đỉnh u trong biến f[u]. Những nhãn thời gian này là những số nguyên giữa 1
và 2|V|, từ lúc có 1 sự kiện được tìm thấy và 1 sự kiện kết thúc cho mỗi |V| đỉnh.
Cho mỗi đỉnh u,
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 18
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
d[u] < f[u] (22.2)
Đỉnh u là màu trắng trước d[u], màu xám giữa d[u] và f[u], và sau đó là màu đen.
Quá trình giải mã theo 1 thuật toán tìm kiếm chiều sâu cơ bản. Đầu vào của
đồ thị G có thể vô hướng hoặc có hướng. Biến time là 1 biến toàn cục mà chúng ta
sử dụng gắn nhãn thời gian.
DFS(G)
1 mỗi đỉnh u є V[G]
Mỗi lần gọi DFS-Visit(u), đỉnh u đầu tiên tô màu trắng. Dòng 1 tô u màu xám,
dòng 2 tăng biến toàn cục time, dòng 3 lưu giá trị biến time mới là biến thời gian
tìm thấy d[u]. Dòng 4-7 kiểm tra đỉnh lân cận v đến u và thực hiện đệ quy thăm v
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 20
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
nếu nó màu trắng. Vì mỗi đỉnh v thuộc Adj[u] được xem xét ở dòng 4, chúng ta nói
rằng cạnh (u,v) được thăm bởi tìm kiếm theo chiều sâu. Cuối cùng, sau khi mỗi
cạnh rời u được thăm, các dòng 8-9 tô đen u và lưu biến kết thúc thời gian trong
f[u].
Lưu ý rằng những kết quả thu được từ tìm kiếm theo chiều sâu có thể phụ
thuộc sự sắp xếp những đỉnh được kiểm tra ở dòng 5 của DFS và sự sắp xếp vào
những đỉnh lân cận đã được thăm ở dòng 4 của DFS-Visit. Thứ tự thăm khác nhau
có khuynh hướng không phải là nguyên nhân những vấn đề bình thường, vì bất kì
kết quả tìm kiếm theo chiều sâu có thể luôn được sử dụng có hiệu quả, với những
kết quả tương đương thiết yếu.
Thời gian thực hiện của DFS là gì? Những vòng lặp ở dòng 1-3 và dòng 5-7
của DFS nhận thời gian Ө(V), loại trừ thời gian để thực hiện lời gọi DFS-Visit.
Như chúng ta đã làm trong tìm kiếm theo chiều sâu, chúng ta sử dụng phân tích
tổng thể. Thủ tục DFS-Visit được gọi chính xác 1 lần trong mỗi đỉnh v є V, DFS-
Visit chỉ được kéo theo trên những đỉnh màu trắng và điều đầu tiên nó làm là sơn
đỉnh màu xám. Suốt quá trình thực hiện của DFS-Visit(v), vòng lặp trên dòng 4-7
được thực hiện |Adj[v]| lần. Từ khi
∑ |Adj[v]| = Ө(E),
i є V
tổng giá trị thực hiện dòng 4-7 cúa DFS-Visit là Ө(E). Thời gian thực hiện của
DFS là Ө(V+E).
Những thuộc tính của tìm kiếm chiều sâu.
Tìm kiếm chiều sâu mang lại giá trị thông tin về cấu trúc của đồ thị. Có lẽ thuộc
tính cơ bản nhất của tìm kiếm theo chiều sâu là đồ thị con ở trước G
π
gian tìm kiếm và thời gian kết thúc của đỉnh tương ứng. Các cạnh được chỉ ra. Nếu 2
khoảng cách gối lên nhau, thì 1 cái được thêm vào trong cái kia, và đỉnh tương ứng đến
khoảng cách nhỏ hơn là con của đỉnh tương ứng đến lớn hơn. (c) Đồ thị của phần vẽ lại
với tất cả cây và các cạnh trước giảm(going down) trong 1 cây tìm kiếm chiều sâu và tất
cả các cạnh sau tăng (going up) từ con đến gốc.
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 23
CÁC THUẬT TOÁN CƠ BẢN VỀ ĐỒ THỊ
Chứng minh Chúng ta bắt đầu trong trường hợp d[u] <d[v]. Có 2 trường hợp được
xem xét, dựa theo d[v] <f[u] hoặc không. Trường hợp thứ nhất xảy ra khi d[v] <
f[u], vì đỉnh v được tìm thấy trong khi đỉnh u vẫn con tô xám. Điều này ngụ ý rằng
v là con u. Hơn nữa, từ khi v được tìm thấy sớm hơn u, tất cả những cạnh rời nó
(outgoing) đã được thăm, và kết thúc v, trước khi tìm kiếm quay lại và kết thúc u.
Trong trường hợp này, vì thế khoảng [d[v],f[v]] được chứa trong toàn bộ khoảng
[d[u],f[u]]. Trong trường hợp khác, f[u] < d[v], và những ngụ ý khác nhau là các
khoảng [d[u],f[u]] và [d[v],f[v]] được tách riêng. Bởi vì các khoảng được tách
riêng, không đỉnh nào được tìm thấy trong khi đỉnh khác màu xám, và vì thế không
đỉnh nào là con của đỉnh khác.
Trong trường hợp d[v] < d[u] cũng tương tự, với vai trò của u và v đảo
ngược.
Hệ quả 22.8 ( các khoảng con lồng nhau )
Đỉnh v thích hợp là con của đỉnh u trong rừng tìm kiếm chiều sâu cho đồ thị G (có
hướng hay vô hướng) khi và chỉ khi d[u] < d[v] < f[v] < f[u].
Chứng minh từ định lý 22.7
Định lý tiếp theo cho đặc trưng quan trọng khác khi 1 đỉnh là con của đỉnh
khác trong rừng tìm kiếm chiều sâu.
Định lý 22.9 ( định lý đường đi màu trắng)
Trong rừng tìm kiếm chiều sâu của 1 đồ thị ( có hướng hay vô hướng) G = (V,E),
đỉnh v là con của đỉnh u nếu và chỉ nếu tại thời điểm d[u] mà tìm kiếm phát hiện u,
đỉnh v có thể đi đến từ u dọc theo 1 con đường được xem là toàn những đỉnh màu
trắng.
tree nếu v tìm thấy đầu tiên bằng cách thăm cạnh (u,v).
2. Các cạnh sau là những cạnh (u,v) nối với 1 đỉnh u đến đỉnh gốc v trong cây
tìm kiếm chiều sâu. Các khuyên có thể xảy ra trong các đồ thị có hướng,
được xem là các cạnh sau
3. Các cạnh trước là các cạnh nontree (u,v) nối với 1 đỉnh u đến đỉnh con v
trong cây chiều sâu
4. Các cạnh chéo là những cạnh còn lại. Chúng có thể đi giữa những đỉnh
trong cùng 1 cây chiều sâu, miễn là đỉnh đó không phải là 1 gốc của cây
khác, hoặc chúng có thể đi giữa các đỉnh trong các cây chiều sâu khác nhau.
Trong hình 22.4 và 22.5, các cạnh được dán nhãn để chỉ loại của chúng. Hình 22.5
(c) cũng trình bày cách đồ thị của hình 22.5 (a) có thể vẽ lại để tất cả các cây và
các cạnh trước hướng xuống trong cây chiều sâu, và tất cả các cạnh sau đi lên. Bất
kì đồ thị nào có thể được vẽ lại theo cách làm này.
Thuật toán DFS có thể sửa đổi để phân loại các cạnh khi nó gặp chúng. Ý
tưởng chìa khóa đó là mỗi cạnh (u,v) có thể phân loại bởi màu sắc của đỉnh v mà
Tiểu luận Thiết kế và phân tích thuật toán - Nhóm 4 Trang 25
Copyright: Tài liệu đại học ©