Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 7: Cấu trúc dữ liệu đồ thị - Nguyễn Khánh Phương

p tôpô
4. Phát hiện chu trình
5. Định hướng đồ thị
6. Đồ thị hai phía
7. Đường đi từ s đến t
8. Tìm đường đi dài nhất trên cây
9. Bài toán tìm bao đóng truyền ứng
10. Tìm cầu, rẽ nhánh của đồ thị vô hướng liên thông
6. Đồ thị hai phía
Cho đồ thị vô hướng G = (V, E). Hỏi đồ thị G có phải là đồ thị hai phía hay không?
Trả lời: Tiến hành tô màu mỗi đỉnh của đồ thị bởi 1 trong hai màu: đen hoặc đỏ. 
Thực hiện thuật toán BFS trên đồ thị G để tô màu các đỉnh trên đồ thị. 
• Đỉnh nguồn: tô màu đen (cho vào tập đỉnh V1)
• Tất cả các đỉnh kề với nó: tô màu đỏ (cho vào tập đỉnh V2)
• Tổng quát:
 – Những đỉnh đến được từ đỉnh nguồn bởi số cạnh là lẻ: tô màu đỏ
 – Những đỉnh đến được từ đỉnh nguồn bởi số cạnh là chẵn: tô màu đen.
Trong quá trình thực hiện tô màu, nếu ta phát hiện ra hai đỉnh kề nhau có cùng màu
 đồ thị đã cho không phải là hai phía
Các ứng dụng của BFS/DFS
1. Tính liên thông của đồ thị
2. Kiểm tra tính liên thông mạnh
3. Sắp xếp tôpô
4. Phát hiện chu trình
5. Định hướng đồ thị
6. Đồ thị hai phía
7. Đường đi từ s đến t
8. Tìm đường đi dài nhất trên cây
9. Bài toán tìm bao đóng truyền ứng
10. Tìm cầu, rẽ nhánh của đồ thị vô hướng liên thông
Tìm đường đi
Bài toán tìm đường đi
• Input: Đồ thị G = (V,E) xác định bởi danh sách kề và hai đỉnh s, t.
• Output: Đường đi từ đỉnh s đến đỉnh t, hoặc khẳng định không tồn tại
 đường đi từ s đến t.
Thuật toán: Thực hiện DFS(s) (hoặc BFS(s)).
 – Nếu truoc[t] == NULL thì không có đường đi, trái lại ta có đường đi
 t  truoc[t]  truoc[truoc[ t]]  . . .  s
Chú ý: BFS tìm được đường đi ngắn nhất theo số cạnh.
DFS giải bài toán đường đi
 (* Main Program*) DFS(s)
 1. for u V { 1. color[s]  xám //Thăm đỉnh s 
 2. color[u]  trắng 2. for each v Adj[s] 
 3. truoc[u]  NULL } 3. if (color[v] == trắng) {
 4. DFS(s) 4. truoc[v]  s
 5. DFS(v) 
 6. }
BFS giải bài toán đường đi
 (* Main Program*) BFS(s)
 1. for u V { 1. color[s]  xám //Thăm đỉnh s
 2. color[u]  trắng 2. truoc[s]  null;
 3. Q ; enqueue(Q,s); // Nạp s vào Q 
 3. truoc[u]  NULL }
 4. while (Q ) 
 4. BFS(s)
 5. {
 6. u  dequeue(Q); // Lấy u khỏi Q
 7. for v Adj[u]
 8. if (color[v] == trắng) //chưa thăm
 9. {
 10. color[v]  xám; //đã thăm
 11. truoc[v]  u;
 12. enqueue(Q,v) //Nạp v vào Q
 13. }
 14. }
Các ứng dụng của BFS/DFS
1. Tính liên thông của đồ thị
2. Kiểm tra tính liên thông mạnh
3. Sắp xếp tôpô
4. Phát hiện chu trình
5. Định hướng đồ thị
6. Đồ thị hai phía
7. Đường đi từ s đến t
8. Tìm đường đi dài nhất trên cây
9. Bài toán tìm bao đóng truyền ứng
10. Tìm cầu, rẽ nhánh của đồ thị vô hướng liên thông
8. Tìm đường đi dài nhất trên cây
Yêu cầu: Cho cây T = (V, E). Tìm đường đi dài nhất trên cây
Ví dụ: Đường đi dài nhất có độ dài = 5 trên
cây là 8 – 6 – 1 – 2 – 4 – 5
Bổ đề: Thực hiện thuật toán BFS (DFS) từ
một đỉnh x bất kỳ của cây, tìm đỉnh mà độ dài của đường đi từ x đến nó là
dài nhất. Kí hiệu đó là u. Khi đó u là đỉnh đầu/cuối của đường đi có độ dài
dài nhất trên cây đã cho.
8. Tìm đường đi dài nhất trên cây
Yêu cầu: Cho cây T = (V, E). Tìm đường đi dài nhất trên cây
Thuật toán: thực hiện 2 lần BFS (DFS)
• Thực hiện thuật toán BFS(DFS) từ một đỉnh bất kỳ x của cây, tìm đỉnh
 mà độ dài của đường đi từ x đến nó là dài nhất. Kí hiệu đỉnh đó là u.
• Thực hiện BFS (DFS) từ đỉnh u, tìm đỉnh mà độ dài của đường đi từ u
 đến nó là dài nhất. Kí hiệu nó là v.
Đường đi từ u đến v là đường đi có độ dài lớn nhất trên cây đã cho.
8. Tìm đường đi dài nhất trên cây
9. Tìm đường đi dài nhất trên c
187
Các ứng dụng của BFS/DFS
1. Tính liên thông của đồ thị
2. Kiểm tra tính liên thông mạnh
3. Sắp xếp tôpô
4. Phát hiện chu trình
5. Định hướng đồ thị
6. Đồ thị hai phía
7. Đường đi từ s đến t
8. Tìm đường đi dài nhất trên cây
9. Bài toán tìm bao đóng truyền ứng
10. Tìm cạnh cầu (bridge), đỉnh rẽ nhánh (cut vertex / 
 articulation point) của đồ thị vô hướng liên thông
9. Transitive Closure
Định nghĩa. Bao đóng truyền ứng của đồ thị có hướng G=(V,E) là đồ thị
có hướng G*=(V,E*) với tập đỉnh là tập đỉnh của đồ thị G và tập cạnh
 E*={(u,v)| có đường đi từ u đến v trên G}
Bài toán: Cho đồ thị có hướng G, tìm bao đóng truyền ứng G*
 1 2 1 2
 0 3 0 3
 5 4 5 4
 G
 G* 189
Nhân ma trận Bun
Boolean Matrix multiplication
• Ma trận Bun – là ma trận có tất cả phần tử là 0 hoặc 1
• Để tính tích của hai ma trận Bun A và B ta thay thế
 – phép toán logic AND vào chỗ phép toán số học *
 – phép toán logic OR vào chỗ phép toán số học +
• Cho 2 ma trận kích thước |V|.|V|
 – Với mỗi s và t: tính tích vô hướng của dòng s của ma trận thứ nhất
 với cột t của ma trận thứ hai.
 190
Matrix Multiplication Implementation
• C = A*B (số)
for (s = 0; s < V; s++) 1 2
 for (t = 0; t < V; t++)
 for (i = 0, C[s][t] = 0; i < V; i++) 3
 C[s][t] += A[s][i] * B[i][t]; 0
• C = A*B (bun) 5 4
for (s = 0; s < V; s++)
 for (t = 0; t < V; t++)
 to t
 for (i = 0, C[s][t] = 0; i < V; i++)
 if (A[s][i] && B[i][t]) 012345
 C[s][t] = 1 0 11 1
 s 1 1 1
 2 1 1
 from from 3 1 1 1
 4 1 1
 5 1 1
 191
Sử dụng tích ma trận để tìm bao đóng truyền ứng
• Ta có thể tính bao đóng truyền ứng cho đồ thị có hướng bằng cách xây
 dựng ma trận kề A cho nó, bổ sung các số 1 vào đường chéo rồi tính
 luỹ thừa A|V|
Chứng minh:
 – A2 – với mỗi cặp s và t, ta ghi 1 vào ma trận tích C khi và chỉ khi
 có đường đi từ s đến i và đường đi từ i đến t trong A
 • Xét đến các đường đi độ dài 2
 – A3 – xét đến các đường đi độ dài 3
 – Không cần xét đến các đường đi độ dài lớn hơn |V| bởi vì đường đi
 đơn trên đồ thị có độ dài lớn nhất là |V|
 192
Thời gian tính
• Question: Thuật toán tìm bao đóng truyền ứng vừa mô tả
 đòi hỏi thời gian bao nhiêu ?
• Answer: |V|4
• Question: Liệu có thể tính A2 tiếp đến A4  At với t |V| để
 cải thiện thời gian tính?
• Ans: |V|3 log |V|
 193
Thuật toán Warshall
// n = |V|, Các đỉnh đánh số từ 0 đến n-1
for (i = 0; i < n; i++)
 3
 for (s = 0; s < n; s++) • Time: O(|V| )
 • 2
 for (t=0; t < n; t++) Space: O(|V| )
 if (A[s][i] && A[i][t])
 A[s][t] = 1;
Mệnh đề. Thuật toán tìm được bao đóng truyền ứng với thời gian O(|V|3)
• Chứng minh: Ta chứng minh thuật toán tìm được bao đóng truyền ứng bằng qui nạp.
 – Lần lặp 1: Ma trận có 1 ở vị trí (s,t) iff có đường đi s-t hoặc s-0-t
 – Lần lặp thứ i: Gán phần tử ở vị trí (s,t) giá trị 1 iff có đường đi từ s đến t trong đồ thị không
 chứa đỉnh với chỉ số lớn hơn i (ngoại trừ hai mút)
 – Lần lặp thứ i+1 
 • Nếu có đường đi từ s đến t không chứa đỉnh có chỉ số lớn hơn i – A[s,t] đã có giá trị 1
 • Nếu có đường đi từ s đến i+1 và đường đi từ i+1 đến t, và cả hai đều không chứa đỉnh với chỉ
 số lớn hơn i (ngoại trừ hai mút) thì A[s,t] được gán giá trị 1
 194
Thuật toán Warshall cải tiến
Ta có thể cải tiến thuật toán bằng cách dịch chuyển câu lệnh if A[s][i] lên
trước vòng lặp for trong cùng:
 // n = |V|, Các đỉnh đánh số từ 0 đến n-1
 for (i = 0; i < n; i++)
 for (s = 0; s < n; s++)
 if A[s][i]
 for (t=0; t < n; t++)
 if A[i][t]
 A[s][t] = 1;
Cải tiến này chỉ có tác dụng tăng hiệu quả thực tế của thuật toán, mà
không thay đổi được đánh giá thời gian tính trong tình huống tồi nhất của
thuật toán 195
Áp dụng DFS tìm bao đóng truyền ứng
Mệnh đề. Sử dụng DFS ta có thể xác định bao đóng truyền
ứng sau thời gian O(|V|*(|E|+|V|))
• Chứng minh
 – DFS cho phép xác định tất cả các đỉnh đạt đến được từ một đỉnh
 cho trước v sau thời gian O(|E|+|V|) nếu ta sử dụng biểu diễn đồ thị
 bởi danh sách kề
 – Do đó để xác định bao đóng truyền ứng ta thực hiện DFS với mỗi v
 V tổng cộng thực hiện DFS |V| lần.
 Thời gian tính: O(|V|*(|E|+|V|)).
 196
Kinh nghiệm tính toán
 đồ thị thưa (|E|=10|V|) đồ thị dày (250 đỉnh)
 V W W* AL E WW* A L
 25 0 0 1 0 5000 289 203 177 23
 50 3 1 2 1 10000 300 214 184 38
 125 35 24 23 4 25000 309 226 200 97
 250 275 181 178 13 50000 315 232 218 337
 500 2222 1438 1481 54 100000 326 246 235 784
 W Thuật toán Warshall
 W* Thuật toán Warshall cải tiến
 A DFS sử dụng ma trận kề
 L DFS sử dụng danh sách kề 
 197
Các ứng dụng của BFS/DFS
1. Tính liên thông của đồ thị
2. Kiểm tra tính liên thông mạnh
3. Sắp xếp tôpô
4. Phát hiện chu trình
5. Định hướng đồ thị
6. Đồ thị hai phía
7. Đường đi từ s đến t
8. Tìm đường đi dài nhất trên cây
9. Bài toán tìm bao đóng truyền ứng
10. Tìm cạnh cầu (bridge), đỉnh rẽ nhánh (cut vertex / 
 articulation point) của đồ thị vô hướng liên thông
Đỉnh rẽ nhánh
 Xóa đỉnh 0
 Xóa đỉnh 1
Xóa đỉnh 0 hoặc 1 sẽ
làm tăng số thành phần
liên thông của đồ thị
 Đỉnh 0 và 1 được gọi
 là đỉnh rẽ nhánh
Tìm đỉnh rẽ nhánh
Yêu cầu: Tìm đỉnh rẽ nhánh (cut vertex / articulation point) của đơn đồ thị
vô hướng G = (V, E) (không nhất thiết phải liên thông).
Trả lời: 
• Brute force: thời gian tính O(V(V + E)) 
• DFS sửa đổi: thời gian tính O(E + V)
Đỉnh v được gọi là đỉnh rẽ nhánh trên đồ thị G nếu xóa đỉnh v khỏi đồ thị
cùng các cạnh nối chúng sẽ là tăng số thành phần liên thông của đồ thị G
Tìm đỉnh rẽ nhánh: thuật toán brute force
• Brute force: với mỗi đỉnh v của đồ thị
 – Xóa đỉnh v khỏi đồ thị : O(E)
 – Kiểm tra tính liên thông của đồ thị bằng BFS/DFS : O(V+E)
 (nếu đồ thị không liên thông đỉnh v là đỉnh rẽ nhánh)
 – Thêm lại đỉnh v vào đồ thị : O(E)
 Thời gian tính là O(V(V + E)) 
Tìm đỉnh rẽ nhánh: thuật toán brute force
• adj[][]: ma trận kề kích thước VxV (adj[i][j]=1 nếu trên đồ thị
 có cạnh (i, j); trái lại = 0)
• count: trả về số đỉnh rẽ nhánh trên đồ thị
• cutVertex[i] = true nếu đỉnh i là đỉnh rẽ nhánh (i
Tìm đỉnh rẽ nhánh: thuật toán brute force
 203
Tìm đỉnh rẽ nhánh: thuật toán DFS sửa đổi
 Cạnh ngược (4, 2) nối đỉnh 4 với tổ
 tiên của nó là đỉnh 2 nếu xóa
 đỉnh 3 (cha của 4 trên cây DFS) 
 DFS(0)
 khỏi đồ thị, vẫn tồn tại đường đi
 giữa 2 và 4 thông qua cạnh ngược
 (4, 2)
Nếu tồn tại cạnh ngược (v, w) trên cây DFS: thì dù xóa đỉnh u là cha của v 
trên cây DFS, ta vẫn có thể đi từ v đến w thông qua cạnh ngược (v, w) 
xóa u không làm tăng số thành phần liên thông của đồ thị u không phải
là đỉnh rẽ nhánh w
 Đỉnh u là đỉnh rẽ nhánh khi nào ??
Đỉnh u là đỉnh rẽ nhánh khi nào ??
Giả sử trên cây DFS, đỉnh u có con là đỉnh
v sao cho trên cây con T(v) có gốc tại v:
(a) Có đỉnh x kề với đỉnh y (y được thăm
 trước đỉnh u), tức là (x, y) là cạnh
 y
 ngược nếu u bị xóa khỏi đồ thị, vẫn
 tồn tại đường đi từ một đỉnh bất kỳ
 trên T(v) đến y nếu điều này đúng
 với tất cả các con của u thì đỉnh u 
 không phải là đỉnh rẽ nhánh
(b) không có đỉnh nào (gọi chung là x) kề
 với đỉnh y là đỉnh được thăm trước
 đỉnh u trên cây DFS (tức là không tồn
 tại cạnh ngược (x, y)) khi đó, nếu x
 xóa đỉnh u khỏi đồ thị, sẽ không tồn
 tại đường đi giữa 1 đỉnh bất kỳ trên
 T(v) và một đỉnh được thăm trước (a) (b)
 đỉnh u cây T(v) sẽ bị ngắt kết nối
 khỏi đồ thị nếu đỉnh u bị xóa khỏi đồ
 thị đỉnh u là đỉnh rẽ nhánh
Đỉnh u là đỉnh rẽ nhánh khi nào ??
Đỉnh u là đỉnh rẽ nhánh nếu một trong hai trường hợp sau xảy ra:
• u là gốc của cây DFS và u có nhiều hơn 1 con
• u không là gốc cây DFS và u có 1 con v sao cho không có đỉnh nào trên cây T(v) 
 kề với tổ tiên của u trên cây DFS (tức là không tồn tại cạnh ngược nối một đỉnh
 thuộc T(v) với một đỉnh tổ tiên của u)
 Xác định trường hợp này thế nào???
 y
 x
Đỉnh u là đỉnh rẽ nhánh khi nào ??
Với mỗi đỉnh u: lưu
• d[u] là thời điểm bắt đầu thăm đỉnh u
• low[u] = d[w]: với w là nút có thời điểm thăm nhỏ nhất, trong đó w là tổ tiên của u, x là
 đỉnh thuộc cây T(u) (x cũng có thể là u), và có cạnh (x, w) (tức là cạnh ngược) trên đồ thị
low[u] = min {d[u], min {d[y]: tồn tại cạnh ngược (x, y) với x là con cháu của u, y là tổ
tiên của u}}
Cách tính low[u]: giả sử đang gọi DFS(u)
• Khởi tạo: low[u] = d[u]
• For each v Adj[u]:
 – Cạnh cây (u, v): low[u] = min (low[u], low[v]) v chưa thăm: visited[v]=false
 – Cạnh ngược (u, v): low[u] = min(low[u], d[v]) • v đã thăm: visited[v]=true
 • parent[u]!=v
Đỉnh u là đỉnh rẽ nhánh khi nào ??
Đỉnh u là đỉnh rẽ nhánh nếu một trong hai trường hợp sau xảy ra:
• u là gốc của cây DFS và u có nhiều hơn 1 con
• u không là gốc cây DFS và u có 1 con v sao cho không có đỉnh nào trên cây T(v) 
 kề với tổ tiên của u trên cây DFS (tức là không tồn tại cạnh ngược nối một đỉnh
 thuộc T(v) với một đỉnh tổ tiên của u)
 Xác định trường hợp này thế nào???
 y
 if (parent[u] != NULL && low[v] >=d[u]) 
 cutVertex[u] =true;
 x
 void main()
Tìm đỉnh rẽ nhánh 1. for each u V
 2. parent[u] = NULL;
 3. visited[u] = false;
 4. cutVertex[u] = false;
 5. time = 0;
 6. for each u V
DFS(u) 7. if (visited[u] == false) DFS(u);
1. visited[u] = true; //Thăm đỉnh u 8. for each u V //In danh sách đỉnh rẽ nhánh
2. d[u] = low[u] = ++time; 9. if (cutVertex[u]) 
3. numChild =0; 10. cout<<u<<endl;
4. for each v Adj[u] 
5. if (visited[v] == false) {
6. numChild++;
7. parent[v]  u;
8. DFS(v);
9. low[u] = min(low[u], low[v]);
10. //TH1: u là gốc của DFS và có nhiều hơn 1 con:
11. if (parent[u] = NULL && numChild >1) cutVertex[u] = true;
12. //TH2: u không là gốc của cây DFS và giá trị low của đỉnh con cháu >= d[v]
13. if (parent[u] != NULL && low[v] >=d[u]) cutVertex[u] =true;
14. }
15. else if (parent[u] != v) low[u] = min(low[u], d[v]); 209
Tìm cạnh cầu
Yêu cầu: Tìm tất cả cạnh cầu (bridge) của đơn đồ thị vô hướng G = (V, E) 
Trả lời: 
• Brute force: thời gian tính O(E(V + E)) 
• DFS sửa đổi: thời gian tính O(E + V)
Cạnh (u, v) được gọi là cạnh cầu trên đồ thị G nếu xóa cạnh (u, v) sẽ
không còn đường đi giữa đỉnh u và v trên đồ thị G
Tìm cạnh cầu: thuật toán brute force
• Brute force: với mỗi cạnh (u, v) của đồ thị
 – Xóa cạnh (u, v) khỏi đồ thị : O(1)
 – Kiểm tra tính liên thông của đồ thị bằng BFS/DFS : O(V+E)
 (nếu đồ thị không liên thông cạnh (u, v) là cạnh cầu
 – Thêm lại cạnh (u, v) vào đồ thị : O(1)
 Thời gian tính là O(E(V + E)) 
(đồ thị biểu diễn bởi ma trận kề)
Tìm cạnh cầu: thuật toán brute force O(E(V+E))
• adj[][]: ma trận kề kích thước VxV
• bridge[e] = true nếu cạnh e là cạnh cầu (e
Tìm cạnh cầu: thuật toán DFS sửa đổi
(u, v) là cạnh cầu nếu: sau khi xóa cạnh (u, v) khỏi đồ thị, thì trên đồ thị sẽ
không còn tồn tại đường đi giữa u và v
Với mỗi cạnh (u, v) (với d[u] < d[v] trên cây DFS): 
 Nếu có cạnh ngược từ v tới tổ tiên của u tức là low[v] <= d[u]
thì tồn tại một đường đi khác giữa u và v bằng cách đi qua cạnh ngược đó
 (u, v) không phải là cạnh cầu
 Nếu low[v] > d[u] thì (u, v) là cạnh cầu
 void main()
Tìm cạnh cầu 1. for each u V
 2. parent[u] = NULL;
 3. visited[u] = false;
 4. time = 0;
 5. for each u V
 6. if (visited[u] == false) DFS(u);
 DFS(u)
 1. visited[u] = true; //Thăm đỉnh u 
 2. d[u] = low[u] = ++time;
 3. for each v Adj[u] 
 4. if (visited[v] == false) {
 5. parent[v]  u;
 6. DFS(v);
 7. low[u] = min(low[u], low[v]);
 8. if (low[v] >d[u]) print(canh cau (u, v));
 9. }
 10. else if (parent[u] != v) low[u] = min(low[u], d[v]); 214