Bài giảng Toán rời rạc 2 - Chương 3: Tìm kiếm trên đồ thị

TÌM KIẾM TRÊN ĐỒ THỊ
Toán rời rạc 2
Nội dung
• Thuật toán tìm kiếm theo chiều sâu trên đồ thị. 
• Thuật toán tìm kiếm theo chiều rộng trên đồ thị. 
• Ứng dụng của thuật toán tìm kiếm theo chiều sâu. 
• Ứng dụng của thuật toán tìm kiếm theo chiều rộng.
2
Thuật toán tìm kiếm theo chiều 
sâu (Depth First Search)
DFS
Tư tưởng
• Trong quá trình tìm kiếm, ưu tiên “chiều sâu” hơn “chiều 
rộng” 
– Đi xuống sâu nhất có thể trước khi quay lại
• Bắt đầu tại một đỉnh v0 nào đó, chọn một đỉnh u bất kỳ 
kề với v0 và lấy nó làm đỉnh duyệt tiếp theo.
– Cách duyệt tiếp theo được thực hiện tương tự như đối với đỉnh 
v0 với đỉnh bắt đầu là u.
• Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta 
sử dụng một mảng chuaxet[] gồm n phần tử (tương ứng 
với n đỉnh):
– Nếu đỉnh thứ u đã được duyệt, phần tử tương ứng trong mảng 
chuaxet[u] có giá trị FALSE.
– Ngược lại, nếu đỉnh chưa được duyệt, phần tử tương ứng trong 
mảng có giá trị TRUE.
4
Biểu diễn thuật toán DFS
• DFS(u) có thể được mô tả bằng thủ tục đệ qui như sau:
Thuật toán DFS (u): //u là đỉnh bắt đầu duyệt 
Begin 
; //Duyệt đỉnh u 
chuaxet[u] := FALSE; //Xác nhận đỉnh u đã duyệt 
for each v Ke(u) do //Lấy mỗi đỉnh v Ke(u). 
If (chuaxet[v] ) then //Nếu đỉnh v chưa duyệt 
DFS(v); //Duyệt theo chiều sâu bắt từ đỉnh v 
EndIf; 
EndFor; 
End.
5
Thuật toán DFS(u) dùng ngăn xếp
(khử đệ qui)
6
Độ phức tạp thuật toán DFS
• Độ phức tạp thuật toán DFS(u) phụ thuộc vào 
phương pháp biểu diễn đồ thị
– Độ phức tạp thuật toán là O(n2) trong trường hợp đồ 
thị biểu diễn dưới dạng ma trận kề, với n là số đỉnh 
của đồ thị.
– Độ phức tạp thuật toán là O(n.m) trong trường hợp 
đồ thị biểu diễn dưới dạng danh sách cạnh, với n là 
số đỉnh của đồ thị, m là số cạnh của đồ thị.
– Độ phức tạp thuật toán là O(max(n, m)) trong trường 
hợp đồ thị biểu diễn dưới dạng danh sách kề, với n là 
số đỉnh của đồ thị, m là số cạnh của đồ thị.
7
Kiểm nghiệm thuật toán DFS (1/3)
• Ví dụ 1: Cho đồ thị gồm 13 đỉnh như hình vẽ. 
Hãy kiểm nghiệm thuật toán DFS(1).
8
Kiểm nghiệm thuật toán DFS (2/3)
9
Kiểm nghiệm thuật toán DFS (3/3)
10
Ví dụ 2
• Cho đồ thị gồm 13 
đỉnh được biểu diễn 
dưới dạng ma trận kề 
như hình bên phải. 
Hãy cho biết kết quả 
thực hiện thuật toán 
trong DFS bắt đầu tại 
đỉnh u=1? Chỉ rõ trạng 
thái của ngăn xếp và 
tập đỉnh được duyệt 
theo mỗi bước thực 
hiện của thuật toán?
11
Ví dụ 2: Kiểm nghiệm thuật toán DFS(1)
12
Cài đặt thuật toán
• Hàm Init(): đọc dữ liệu theo khuôn dạng từ file dothi.in và thiết 
lập mảng chuaxet[u] =True (u=1, 2,..,n).
• Hàm DFS_Dequi: Cài đặt thuật toán DFS(u) bằng đệ qui.
• Hàm DFS_Stack: Cài đặt thuật toán DFS(u) dựa vào stack.
13Xem code minh họa
Thuật toán tìm kiếm theo chiều 
rộng (Breadth First Search)
Tư tưởng
• Trong quá trình tìm kiếm, ưu tiên “chiều rộng” hơn “chiều 
sâu” 
• Tìm kiếm xung quanh trước khi đi xuống sâu hơn
• Đỉnh được nạp vào hàng đợi đầu tiên là u
– Các đỉnh kề với u là ( v1, v2, . . ., vk) được nạp vào hàng đợi nếu 
như nó chưa được xét đến.
• Quá trình duyệt tiếp theo được bắt đầu từ các đỉnh còn 
có mặt trong hàng đợi.
• Thuật toán dừng khi hàng đợi rỗng.
15
Thuật toán BFS
16
Độ phức tạp thuật toán BFS
• Độ phức tạp thuật toán BFS(u) phụ thuộc vào 
phương pháp biểu diễn đồ thị
– Độ phức tạp thuật toán là O(n2) trong trường hợp đồ 
thị biểu diễn dưới dạng ma trận kề, với n là số đỉnh 
của đồ thị.
– Độ phức tạp thuật toán là O(n.m) trong trường hợp 
đồ thị biểu diễn dưới dạng danh sách cạnh, với n là 
số đỉnh của đồ thị, m là số cạnh của đồ thị.
– Độ phức tạp thuật toán là O(max(n, m)) trong trường 
hợp đồ thị biểu diễn dưới dạng danh sách kề, với n là 
số đỉnh của đồ thị, m là số cạnh của đồ thị.
17
Kiểm nghiệm thuật toán BFS (1/2)
• Ví dụ 3. Cho đồ thị 
gồm 13 đỉnh được 
biểu diễn dưới dạng 
ma trận kề như hình 
bên phải. Hãy cho biết 
kết quả thực hiện thuật 
toán BFS bắt đầu tại 
đỉnh u=1? Chỉ rõ trạng 
thái của hàng đợi và 
tập đỉnh được duyệt 
theo mỗi bước thực 
hiện của thuật toán?
18
Kiểm nghiệm thuật toán BFS (2/2)
19
Lưu ý
• Với đồ thị vô hướng
– Nếu DFS(u) = V hoặc BFS(u) = V, ta có thể kết 
luận đồ thị liên thông
• Với đồ thị có hướng
– Nếu DFS(u) = V hoặc BFS(u) = V, ta có thể kết 
luận đồ thị liên thông yếu
20
Cài đặt thuật toán
• Hàm Init(): đọc dữ liệu theo khuôn dạng từ file dothi.in và thiết 
lập mảng chuaxet[u] =True (u=1, 2,..,n).
• Hàm BFS_Dequi: Cài đặt thuật toán BFS(u) bằng hàng đợi.
21Xem code minh họa
Ứng dụng của thuật toán DFS và 
BFS
Vài ứng dụng cơ bản của DFS và BFS
• Duyệt tất cả các đỉnh của đồ thị.
• Duyệt tất cả các thành phần liên thông của đồ thị.
• Tìm đường đi từ đỉnh s đến đỉnh t trên đồ thị.
• Duyệt các đỉnh trụ trên đồ thị vô hướng.
• Duyệt các đỉnh trụ trên đồ thị vô hướng.
• Duyệt các cạnh cầu trên đồ thị vô hướng.
• Định chiều đồ thị vô hướng.
• Duyệt các đỉnh rẽ nhánh của cặp đỉnh s, t.
• Xác định tính liên thông mạnh trên đồ thị có hướng.
• Xác định tính liên thông yếu trên đồ thị có hướng.
• Thuật toán tìm kiếm theo chiều rộng trên đồ thị.
• Xây dựng cây khung của đồ thị vô hướng liên thông
23
Xác định thành phần liên thông của đồ thị
• Phát biểu bài toán:
– Cho đồ thị đồ thị vô hướng G=, trong đó V là 
tập đỉnh, E là tập cạnh. Xác định các thành phần liên 
thông của G =?
• Thuật toán:
24
Kiểm nghiệm thuật toán
• Cho đồ thị được biểu diễn dưới dạng ma trận kề:
• Kết quả:
– Thành phần liên thông 1: BFS(1) = { 1, 3, 5, 7, 9, 11, 13}. 
– Thành phần liên thông 2: BFS(2) = {2, 4, 6, 8, 10, 12}. 
25
Cài đặt thuật toán
• Hàm Init(): Đọc dữ liệu theo khuôn dạng và khởi đầu mảng 
chuaxet[u] = True (1 i n). 
• Hàm BFS (u), DFS(u) : Hai thuật toán duyệt theo chiều 
rộng và duyệt theo chiều sâu được sử dụng để xác định các 
thành phần liên thông.
26
Xem code minh họa
Tìm đường đi giữa các đỉnh trên đồ thị
• Phát biểu bài toán
– Cho đồ thị G = (vô hướng hoặc có hướng), trong đó V là 
tập đỉnh, E là tập cạnh. Tìm đường đi từ đỉnh s V đến đỉnh t V?
• Mô tả thuật toán
– Nếu t ∈ DFS(s) hoặc t ∈ BFS(s) thì ta có thể kết luận có đường đi 
từ s đến t trên đồ thị, ngược lại sẽ không có đường đi
– Để ghi nhận đường đi ta sử dụng mảng truoc[] gồm n n phần tử 
(n= |V|)
• Khởi tạo ban đầu truoc[u]=0 với mọi u.
• Mỗi khi đưa v ∈ Ke(u) vào ngăn xếp (nếu sử dụng DFS) hoặc hàng đợi (nếu 
sử dụng BFS) ta ghi nhận truoc[v]=u.
• Nếu DFS và BFS không duyệt được đến đỉnh t, khi đó truoc[t]=0 thì ta kết luận 
không có đường đi từ s đến t.
27
Tìm đường đi giữa các đỉnh trên đồ thị
28
Dùng DFS
Tìm đường đi giữa các đỉnh trên đồ thị
29
Dùng BFS
Tìm đường đi giữa các đỉnh trên đồ thị
30
Ghi nhận đường đi
Kiểm nghiệm thuật toán
• Xác định 
đường đi từ 
đỉnh 1 đến 
đỉnh 13 trên 
đồ thị được 
biểu diễn 
dưới dạng 
ma trận kề
bên:
31
Kiểm nghiệm thuật toán DFS(1)
32
Kiểm nghiệm thuật toán BFS(1)
33
• Lưu ý:
– Đường đi từ đỉnh s đến đỉnh t theo thuật toán BFS đi qua ít nhất 
các cạnh của đồ thị (có độ dài nhỏ nhất).
Cài đặt thuật toán
• Xem code minh họa
34
Tính liên thông mạnh trên đồ thị có hướng
• Phát biểu bài toán:
– Đồ thị có hướng G= liên thông mạnh nếu giữa hai đỉnh bất 
kỳ của nó đều tồn tại đường đi.
– Cho trước đồ thị có hướng G = . Kiểm tra xem G có liên 
thông mạnh hay không?
• Thuật toán:
35
Kiểm nghiệm thuật toán
• Xác định đồ 
thị có hướng 
G = 
được biểu 
diễn dưới 
dạng ma trận 
kề bên có liên 
thông mạnh 
hay không?
36
Kiểm nghiệm thuật toán kiểm tra tính liên 
thông mạnh
37
Cài đặt thuật toán
• Thủ tục Read-Data(): Đọc ma trận kề biểu diễn đồ thị 
trong file dothi.in.
• Thủ tục ReInit(): Khởi tạo lại giá trị cho mảng chuaxet[].
• Thủ tục DFS(u): Thuật toán DFS bắt đầu tại đỉnh u.
• Thủ tục BFS(u): Thuật toán BFS bắt đầu tại đỉnh u.
• Hàm Strong-Conective(): Kiểm tra tính liên thông mạnh 
của đồ thị.
38
Xem code minh họa
Duyệt các đỉnh trụ
• Phát biểu bài toán
– Cho đồ thị vô hướng liên thông G =. Đỉnh u V được gọi trụ 
nếu loại bỏ đỉnh u cùng với các cạnh nối với u làm tăng thành 
phần liên thông của đồ thị.
– Cho đồ thị vô hướng liên thông G = , tìm các đỉnh trụ của G?
• Mô tả thuật toán
– Trong DFS() hoặc BFS(), thiết lập giá trị chuaxet[u] = False.
– Quá trình duyệt sẽ được thực hiện tại một đỉnh bất kỳ v u.
• Nếu DFS(v) = V\{u} hoặc BFS(v) = V\{u}:
– Đồ thị mới nhận được cũng chỉ có 1 thành phần liên thông
– Kết luận v không là trụ.
• Nếu DFS(v) V\{u} hoặc BFS(v) V\{u}:
– Khi đó v chính là trụ vì số thành phần liên thông của đồ thị đã tăng lên.
39
Thuật toán duyệt các đỉnh trụ của đồ thị
40
Kiểm nghiệm thuật toán
• Xác định đồ thị 
vô hướng 
G= 
được biểu 
diễn dưới 
dạng ma trận 
kề bên có 
những đỉnh trụ 
nào?
41
Kiểm nghiệm thuật toán duyệt các đỉnh trụ 
của đồ thị
42
Cài đặt thuật toán
• Thủ tục Read-Data(): Đọc ma trận kề biểu diễn đồ thị 
trong file dothi.in.
• Thủ tục ReInit(): Khởi tạo lại giá trị cho mảng chuaxet[].
• Thủ tục DFS(u): Thuật toán DFS bắt đầu tại đỉnh u.
• Thủ tục BFS(u): Thuật toán BFS bắt đầu tại đỉnh u.
43
Xem code minh họa
Duyệt các cạnh cầu
• Phát biểu bài toán
– Cho đồ thị vô hướng G =. Cạnh e E được gọi là cầu nếu 
loại bỏ e làm tăng thành phần liên thông của đồ thị.
– Cho trước đồ thị vô hướng liên thông G = , tìm tất cả các 
cạnh cầu của đồ thị.
• Mô tả thuật toán
– Đối với đồ thị được biểu diễn dưới dạng ma trận kề:
• Loại bỏ cạnh e=(u,v) E ra khỏi đồ thị ta thực hiện bằng cách cho các phần 
tử A[u][v]=0 và A[v][u]=0.
– Đối với đồ thị được biểu diễn dưới dạng danh sách kề:
• Danh sách kề của đỉnh u ta bớt đi đỉnh v, Ke(u) = Ke(u)\{v}
• Danh sách kề của đỉnh v ta bớt đi đỉnh u, Ke(v) = Ke(v)\{u}.
44
Thuật toán duyệt các cạnh cầu của 
đồ thị
45
Kiểm nghiệm thuật toán
• Xác định đồ thị 
vô hướng 
G= được 
biểu diễn dưới 
dạng ma trận kề 
bên có những 
cạnh cầu nào?
46
Kiểm nghiệm thuật toán duyệt các cạnh cầu 
của đồ thị
47Kết luận: cạnh (3,5), (9,10) là cầu 
Cài đặt thuật toán
• Thủ tục Read-Data(): Đọc ma trận kề biểu diễn đồ thị 
trong file dothi.in.
• Thủ tục ReInit(): Khởi tạo lại giá trị cho mảng chuaxet[].
• Thủ tục DFS(u): Thuật toán DFS bắt đầu tại đỉnh u.
• Thủ tục BFS(u): Thuật toán BFS bắt đầu tại đỉnh u.
48
Xem code minh họa
Duyệt các thành phần liên thông mạnh của 
đồ thị
• Mỗi thành phần liên thông mạnh của đồ thị là một đồ thị 
con của G mà giữa hai đỉnh bất kỳ của đồ thị con đều có 
đường đi.
• Bài toán:
– Liệt kê tất cả các thành phần liên thông mạnh của đồ thị có 
hướng G=.
49
Bài toán định chiều đồ thị (1/2)
• Định nghĩa
– Phép định chiều đồ thị vô hướng liên thông là phép biến đổi đồ 
thị vô hướng liên thông thành đồ thị có hướng liên thông mạnh.
– Đồ thị vô hướng G = có thể dịch chuyển được thành đồ thị 
có hướng liên thông mạnh bằng cách định chiều mỗi cạnh vô 
hướng thành một cung có hướng được gọi là đồ thị định chiều 
được.
50
Bài toán định chiều đồ thị (2/2)
• Định lý
– Đồ thị vô hướng liên thông G = định chiều được khi và chỉ 
khi tất cả các cạnh e E của G đều không phải là cầu.
• Bài toán.
– Cho đồ thị vô hướng liên thông G = . Hãy định chiều đồ thị 
G sao cho ta có thể nhận được đồ thị có hướng với ít nhất thành 
phần liên thông mạnh.
• Một số vấn đề cần quan tâm
– Chứng minh một đồ thị vô hướng là định chiều được.
– Viết chương trình kiểm tra một đồ thị vô hướng có định chiều 
được hay không?
– Chỉ ra một phép định chiều trên một đồ thị vô hướng.
51
Bài tập
• Làm các bài tập từ 1 – 10 trong Bài giảng Toán 
rời rạc 2.
52