Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 6: Đồ thị và một vài cấu trúc phi tuyến khác - Đỗ Tuấn Anh

calls
2
4
3
5
1
7
6
9
8
0
source
Example
Adjacency List
0
1
2
3
4
5
6
7
8
9
Visited Table (T/F)
T
T
T
T
T
T
T
T
T
T
8
9
-
1
3
3
5
6
2
8
PredRDFS( 2 )
RDFS(8)
RDFS(9)
RDFS(1) -> Stop
Recursive
calls
2
4
3
5
1
7
6
9
8
0
source
Example
Adjacency List
0
1
2
3
4
5
6
7
8
9
Visited Table (T/F)
T
T
T
T
T
T
T
T
T
T
8
9
-
1
3
3
5
6
2
8
PredRDFS( 2 )
RDFS(8)
RDFS(9) -> StopRecursive
calls
2
4
3
5
1
7
6
9
8
0
source
Example
Adjacency List
0
1
2
3
4
5
6
7
8
9
Visited Table (T/F)
T
T
T
T
T
T
T
T
T
T
8
9
-
1
3
3
5
6
2
8
PredRDFS( 2 )
RDFS(8) -> Stop
Recursive
calls
2
4
3
5
1
7
6
9
8
0
source
Example
Adjacency List
0
1
2
3
4
5
6
7
8
9
Visited Table (T/F)
T
T
T
T
T
T
T
T
T
T
8
9
-
1
3
3
5
6
2
8
PredRDFS( 2 ) -> Stop
Recursive
calls
2
4
3
5
1
7
6
9
8
0
source
Example
Adjacency List
0
1
2
3
4
5
6
7
8
9
Visited Table (T/F)
T
T
T
T
T
T
T
T
T
T
8
9
-
1
3
3
5
6
2
8
Pred
Try some examples.
Path(0) ->
Path(6) ->
Path(7) ->
Check our paths, does DFS find valid paths? Yes.
2
4
3
5
1
7
6
9
8
0
source
Độ phức tạp thời gian của DFS
(Sử dụng danh sách kề)
z Không bao giờ thăm một nút quá 1 lần
z Thực hiện kiểm tra tất cả cạnh của một đỉnh
{Σv bậc(v) = 2m với m là tổng số cạnh
z Do vậy thời gian tính của DFS tỉ lệ thuận với số
cạnh và số đỉnh (giống BFS)
{O(n + m)
z Hoặc viết:
{O(|v|+|e|) |v| = tổng số đỉnh (n)
|e| = tổng số cạnh (m)
Depth-First Search
a
lg
f
b
c ed
j
k
ih
DFS đảm bảo thăm mọi đỉnh liên thông với đỉnh ban đầu.
Cho phép xác định đồ thị có liên thông không, và tìm các thành phần liên
thông của đồ thị.
Ứng dụng của đồ thị
zBài toán bao đóng truyền ứng (transitive 
closure)
zBài toán sắp xếp topo (topological sort)
Bài toán bao đóng truyền ứng
zĐặt vấn đề: Cho đồ thị G 
{Có đường đi từ A đến B không?
Bao đóng truyền ứng là gì?
zBao đóng truyền ứng của một đồ thị định 
hướng có cùng số nút với đồ thị ban đầu.
zNếu có một đường đi định hướng từ nút a
tới b, thì bao đóng truyền ứng sẽ chứa một 
tới b, thì bao đóng truyền ứng sẽ chứa một
A graph Transitive closure
b
cd
a b
cd
a
Đồ thị Bao đóng truyền ứng
15 4
3
2 0 1 1 0 1
0 0 0 1 1
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
A =
Biểu diễn đồ thị dưới dạng ma trận kề
Kích thước của ma trận
1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
Bao đóng truyền ứng của G(V,E) là
Bao đóng truyền ứng và phép nhân ma trận
Xét
Phép toán logic, AND, OR
Xét ? 
Bao đóng truyền ứng và phép nhân ma trận
Xét ? 
Bao đóng truyền ứng và phép nhân ma trận
Xét ? 
Bao đóng truyền ứng và phép nhân ma trận
Giải thuật Warshall
Algorithm Warshall (A, P, n)
Input: A là ma trận kề biểu diễn đồ thị,
n là số đỉnh của đồ thị
Output: P là bao đóng truyền ứng của đồ thị
1. P = A;
2. for k = 1 to n do
3. for i = 1 to n do
4. for j = 1 to n do
5. P[i][j] = P[i][j] | P[i][k] & P[k][j];
Độ phức tạp của phép nhân 2 ma trận
kích thước nxn? 
Thực hiện bao nhiêu phép nhân ma trận
kích thước nxn?
Độ phức tạp
Bài toán sắp xếp topo
Ví dụ: Cấu trúc môn học
TRRCTDL KTMT
211 251
TTKH
271 252TCCGT
231
KTLT
221
361
362
381303
327
336
341
343
342
332
334
NMTH
Đồ thị định hướng, không có chu trình
zMột đồ thị định hướng là một chuỗi các đỉnh
(v0, v1, . . . , vk)
{(vi, vi+1) được gọi là một cung (k gọi là cạnh)
zMột chu trình định hướng là một đường đi định
hướng với đỉnh đầu trùng với đỉnh cuối.
zMột đồ thị định hướng không có chu trình nếu
nó không chứa bất kỳ chu trình định hướng nào
Ứng dụng của đồ thị định hướng
z Đồ thị định hướng thường được sử dụng để thể hiện các
công việc có thứ tự phụ thuộc
z Có nghĩa là công việc này chỉ bắt đầu khi công việc kia
kết thúc
z Các quan hệ thứ tự ràng buộc đó được thể hiện bằng
các cung
z Một cung (i,j) có nghĩa là công việc j không thể bắt đầu
cho đến khi công việc i kết thúc
z Rõ ràng, để các ràng buộc không bị lặp vô hạn
thì đồ thị phải là không có chu trình. 
i j
Bậc vào và bậc ra
z Vì các cạnh là có định hướng
zPhải xem xét các cung là “đi vào” hay “đi
ra”
{Khái niệm
zBậc vào(v)
zBậc ra(v)
Bậc ra
zTổng số cung đi “ra” khỏi v
zTổng số bậc ra? (m=#số cạnh)
mv
v
=∑
vertex 
)(bac_ra
Bậc vào
zTổng số cung đi “vào” v
zTổng số bậc vào?
mv
v
=∑
vertex 
)(bac_vao
Ví dụ
0
1
2
3
4
5
6
7
8
9
Bậc_vào(2)?
Bậc_vào(8)?
Bậc_ra(0)?
Sắp xếp topo
z Sắp xếp topo là thuật toán cho đồ thị định
hướng không có chu trình
z Nó có thể được xem như việc định ra một thứ
tự tuyến tính cho các đỉnh, với các quan hệ
thứ tự thể hiện bởi các cung
0
1
2
3
4
5
6
7
8
9
Ví dụ:
0, 1, 2, 5, 9
0, 4, 5, 9
0, 6, 3, 7 ?
Sắp xếp topo
z Ý tưởng:
{ Bắt đầu với đỉnh có bậc vào = 0!
{ Nếu không tồn tại, đồ thị là có chu trình
1. Tìm đỉnh i có bậc vào = 0. Ghi vào dãy thứ
tự tuyến tính
2. Xóa đỉnh i và các cung đi ra khỏi đỉnh i khỏi
đồ thị
3. Đồ thị mới vẫn là định hướng không có chu
trình. Do đó, lặp lại bước 1-2 cho đến khi
không còn đỉnh nào trong đồ thị.
Giải thuật
Tìm tất cả đỉnh bắt đầu
Giảm bậc vào(w)
Thêm các đỉnh bắt đầu
mới vào Q
Ví dụ
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
1
2
1
1
2
1
1
2
2
Bậc vào
start
Q = { 0 }
OUTPUT: 0 
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
1
2
1
1
2
1
1
2
2
Dequeue 0 Q = { }
-> remove 0’s arcs – adjust
indegrees of neighbors
OUTPUT: 
Decrement 0’s
neighbors
-1
-1
-1
Ví dụ Bậc vào
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
2
1
0
2
0
1
2
2
Dequeue 0 Q = { 6, 1, 4 }
Enqueue all starting points
OUTPUT: 0 
Enqueue all
new start points
Ví dụ Bậc vào
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
2
1
0
2
0
1
2
2
Dequeue 6 Q = { 1, 4 } 
Remove arcs .. Adjust indegrees
of neighbors 
OUTPUT: 0 6 
Adjust neighbors
indegree
-1
-1
Ví dụ Bậc vào
1
2
3
4
5
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
1
0
0
2
0
1
2
2
Dequeue 6 Q = { 1, 4, 3 } 
Enqueue 3
OUTPUT: 0 6 
Enqueue new
start
Ví dụ Bậc vào
1
2
3
4
5
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
1
0
0
2
0
1
2
2
Dequeue 1 Q = { 4, 3 } 
Adjust indegrees of neighbors
OUTPUT: 0 6 1 
Adjust neighbors
of 1
-1
Ví dụ Bậc vào
23
4
5
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
2
0
1
2
2
Dequeue 1 Q = { 4, 3, 2 } 
Enqueue 2
OUTPUT: 0 6 1 
Enqueue new 
starting points
Ví dụ Bậc vào
23
4
5
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
2
0
1
2
2
Dequeue 4 Q = { 3, 2 } 
Adjust indegrees of neighbors
OUTPUT: 0 6 1 4 
Adjust 4’s 
neighbors
-1
Ví dụ Bậc vào
23
5
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
1
0
1
2
2
Dequeue 4 Q = { 3, 2 } 
No new start points found
OUTPUT: 0 6 1 4 
NO new start
points
Ví dụ Bậc vào
23
5
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
1
0
1
2
2
Dequeue 3 Q = { 2 } 
Adjust 3’s neighbors
OUTPUT: 0 6 1 4 3 
-1
Ví dụ Bậc vào
25
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
1
0
1
1
2
Dequeue 3 Q = { 2 } 
No new start points found
OUTPUT: 0 6 1 4 3 
Ví dụ Bậc vào
25
7
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
1
0
1
1
2
Dequeue 2 Q = { } 
Adjust 2’s neighbors
OUTPUT: 0 6 1 4 3 2 
-1
-1
Ví dụ Bậc vào
57
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
1
2
Dequeue 2 Q = { 5, 7 } 
Enqueue 5, 7
OUTPUT: 0 6 1 4 3 2 
Ví dụ Bậc vào
57
8
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
1
2
Dequeue 5 Q = { 7 }
Adjust neighbors 
OUTPUT: 0 6 1 4 3 2 5 
-1
Ví dụ Bậc vào
78
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
1
1
Dequeue 5 Q = { 7 }
No new starts 
OUTPUT: 0 6 1 4 3 2 5 
Ví dụ Bậc vào
78
9
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
1
1
Dequeue 7 Q = { }
Adjust neighbors 
OUTPUT: 0 6 1 4 3 2 5 7 
-1
Ví dụ Bậc vào
89
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
0
1
Dequeue 7 Q = { 8 }
Enqueue 8 
OUTPUT: 0 6 1 4 3 2 5 7 
Ví dụ Bậc vào
89
0
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
0
1
Dequeue 8 Q = { }
Adjust indegrees of neighbors
OUTPUT: 0 6 1 4 3 2 5 7 8 
-1
Ví dụ Bậc vào
90
1
2
3
4
5
6
7
8
9
2
6 1 4
7 5
8
5
3 2
8
9
9
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
0
0Dequeue 8 Q = { 9 }
Enqueue 9
Dequeue 9 Q = { }
STOP – no neighbors
OUTPUT: 0 6 1 4 3 2 5 7 8 9
Ví dụ Bậc vào
Ví dụ
OUTPUT: 0 6 1 4 3 2 5 7 8 9
0
1
2
3
4
5
6
7
8
9
Sắp xếp topo: Độ phức tạp
zKhông bao giờ thăm 1 đỉnh nhiều hơn 1 
lần
zVới mỗi đỉnh, phải xét tất cả các cung ra
{Σ bậc_ra(v) = m
zĐộ phức tạp về thời gian: O(n + m)