Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 7: Đồ thị - Nguyễn Duy Hiệp
5/5/2011
Nội dung
Các khái niệm cơ bản
Biểu diễn đồ thị
Thuật toán duyệt đồ thị và ứng dụng
Một số bài toán trên đồ thị
Chương 7
Đồ thị
Đồ thị
Đồ thị – graph: mô tả các mối quan hệ
Mạng Internet
Mạng lưới đường
giao thông
Sơ đồ cấu trúc
điều khiển
Mạng xã hội
Mạch điện
…
Các khái niệm cơ bản
1
5/5/2011
Các khái niệm cơ bản
Các khái niệm cơ bản
Một đồ thị G bao gồm một tập V(G) các đỉnh (nút) và một tập E(G)
các cạnh (cung) là các cặp đỉnh.
Đồ thị vô hướng – undirected graph: Đồ thị G(V,E) là vô
hướng nếu các cạnh (u,v) là một bộ không có thứ tự
Đồ thị có hướng – directed graph: Đồ thị G(V,E) là có
hướng nếu các cạnh (u,v) là một bộ có thứ tự
đỉnh
a
e
i
b
f
c
d
cạnh
g
h
j
k
l
12 đỉnh
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) }
13 cạnh
Undirected graph
Directed graph
Các khái niệm cơ bản
Các khái niệm cơ bản
Đồ thị có trọng số ‐ weighted graph: Đồ thị G(V,E) là có
trọng số nếu các cạnh hoặc đỉnh là được gán một giá trị số
(trọng số)
Đồ thị không trọng số ‐ unweighted graph: Các cạnh, đỉnh
không được gán trọng số hoặc có trọng số giống nhau
Đơn đồ thị ‐ Simple graph: giữa hai đỉnh chỉ tồn tại một
cạnh nếu có
Không phải đơn đồ thị ‐ non‐ simple graph: trên đồ thị
tồn tại một số kiểu cạnh đặc biệt:
Cạnh vòng – self‐loop: xuất phát và kết thúc tại cùng một đỉnh
Đa cạnh – multiedge: một cạnh được lặp lại nhiều hơn một lần
trên đồ thị
2
5
7
4
6
11
Unweighted graph
Weighted graph
Simple graph
Non‐simple graph
2
5/5/2011
Các khái niệm cơ bản
Các khái niệm cơ bản
Đồ thị thưa – Sparse: số cạnh trên đồ thị ít. Thường là tỉ
lệ tuyến tính với số đỉnh
Đồ thị có chu trình – cyclic graph: trong đồ thị có tồn tại
chu trình
Đồ thị dày – Dense: số cạnh trên đồ thị lớn
Đồ thị không có chu trình – acyclic graph: trong đồ thị có
tồn tại chu trình
Sparse graph
Dense graph
Acyclic graph
Cyclic graph
Các khái niệm cơ bản
Các khái niệm cơ bản
Đồ thị tường minh – explicit graph: các phần của đồ thị
được xây dựng tường minh
Đồ thị có nhãn – labeled graph: các đỉnh được gán nhãn
để phân biệt với nhau
Đồ thị không tường minh – implicit graph: các phần của
đồ thị không được xây dựng một cách tường minh, nhưng
sẽ được xây dựng khi chúng ta sử dụng.
Đồ thị không có nhãn – unlabeled graph: các đỉnh là như
nhau (không được phân biệt). VD bài toán kiểm tra hai
đồ thị là đồng hình – isomorphism testing.
Unlabeled graph
Labeled graph
Explicit graph
Implicit graph
3
5/5/2011
Các khái niệm cơ bản
Các khái niệm cơ bản
Đường đi – path giữa hai đỉnh ꢀꢁ, ꢀꢂ là một chuỗi các
đỉnh ꢀꢁ, ꢀꢃ, . . , ꢀꢂ, trong đó ꢄꢀꢅ, ꢀꢅꢆꢁꢇ là một cạnh trên đồ
thị (ꢈ ꢉ 0, . . , ꢊ ꢋ 1)
Bậc‐ degree của đỉnh là số cạnh xuất phát (kết thúc) từ đỉnh đó
Đỉnh u, v là kề nhau – adjacent: nếu tồn tại cạnh nối giữa u,v
Độ dài đường đi: số cạnh trên đường đi (số đỉnh ‐1)
G
Bậc (A) = 1
G
A
A
G
Một đường đi giữa G, D là G, A, B, D
A
Bậc ra (F) = 3
Bậc vào (F) =2
C
Đường đi đơn: các đỉnh không lặp lại
G, A, C, B, D
B
B
F
B
F
Bậc ra (B) = 0
F
G, A, B, C, A, B, D không phải đường đi đơn
Bậc (F) = 3
A kề F nhưng F không kề với A
Cạnh (F, B): F là đỉnh nguồn, B là đỉnh đích
D
A và F là kề nhau
Các khái niệm cơ bản
Chu trình – cycle: đường đi trong đó có điểm đầu và điểm
cuối trùng nhau
Chu trình đơn: không có đỉnh nào trùng nhau trừ đỉnh
đầu và đỉnh cuối
Các khái niệm cơ bản
Đồ thị ꢌꢍꢄꢎꢍ, ꢏꢍꢇ là đồ thị con của ꢌ ꢎ, ꢏ nếu
ꢎꢍ ⊆ ꢎ
ꢏꢍ ⊆ ꢏ
G
G
G
A
A
A
C
C
Chu trình: G, A, B, C, A, B, D, F, G
Chu trình đơn: G, A, B, D, F, G
B
B
B
F
F
F
D
D
ꢌꢍꢄꢎꢍ, ꢏꢍꢇ
D
ꢌꢄꢎ, ꢏꢇ
4
5/5/2011
Các khái niệm cơ bản
Các khái niệm cơ bản
Đồ thị liên thông – connected graph: luôn tồn tại đường
đi giữa hai cặp đỉnh bất kỳ trên đồ thị
Quiz: Cây có phải đồ thị liên thông?
Số cạnh, đnh trên cây?
Connected graph
Not connected graph
Các khái niệm cơ bản
Biểu diễn mạng xã hội: Facebook, LinkedIn, Twister,…
Đồ thị có hướng hay vô hướng?
Có trọng số hay không trọng số?
Có cạnh vòng?
Biểu diễn đồ thị
Số bạn của một thành viên?
Bạn có biết cô ấy/ anh ấy?
….
•Ma trận kề
•Danh sách kề
5
5/5/2011
Biểu diễn đồ thị
Biểu diễn đồ thị
1
Hai phương pháp biểu diễn cơ bản:
2
Ma trận kề (Adjacency Matrix): Biểu diễn ꢌꢄꢎ, ꢏꢇ Dùng ma
trận ꢐ kích thước ꢑ ꢒ ꢑ (trong đó ꢎ ꢉ ꢑ). Nếu tồn tại
cạnh giữa đỉnh ꢈ và ꢓ thì ꢐ ꢈ, ꢓ ꢉ 1, ngược lại bằng 0.
4
3
5
Ma trận kề
6
Danh sách kề (Adjacency List): Biểu diễn ꢌꢄꢎ, ꢏꢇ dùng
mảng các danh sách móc nối. Mỗi danh sách móc nối tương
ứng với 1 đỉnh chứa danh sách các đỉnh kề với đỉnh đó.
Danh sách kề
Biểu diễn đồ thị
Ma trận kề và danh sách kề
Quiz. Biểu diễn đồ thị có hướng ꢌꢄꢎ, ꢏꢇ sau
Ma trận kề
Danh sách kề
Kiểm tra cạnh
ꢕꢄ1ꢇ
ꢕꢄmaxꢄꢖꢗꢘꢙꢗꢗ ꢔ , ꢖꢗꢘꢙꢗꢗ ꢀ ꢇꢇ
A
ꢄꢔ, ꢀꢇ
Tìm bậc của ꢔ
ꢕꢄꢑꢇ
ꢕꢄꢖꢗꢘꢙꢗꢗꢄꢔꢇꢇ
ꢕꢄ ꢎ ꢚ |ꢏ|ꢇ
B
ꢃ
Kích thước bộ nhớ
ꢕꢄ ꢎ ꢇ
ꢕꢄ1ꢇ
F
Ma trận kề
C
Thêm xóa cạnh
ꢕꢄmaxꢄꢖꢗꢘꢙꢗꢗ ꢔ , ꢖꢗꢘꢙꢗꢗ ꢀ ꢇꢇ
ꢄꢔ, ꢀꢇ
ꢃ
E
Duyệt trên đồ thị
ꢕꢄ ꢎ ꢇ
ꢕꢄ ꢎ ꢚ |ꢏ|ꢇ
D
NOTE: Nên dùng danh sách kề để biểu diễn các đồ thị trong trường
hợp tổng quát
Danh sách kề
6
5/5/2011
Biểu diễn đồ thị
Biểu diễn đồ thị
#define MAXV 1000 /* maximum number of vertices */
typedef struct {
int y; /* adjacency info */
int weight; /* edge weight, if any */
struct NODE *next; /* next edge in list */
} NODE;
typedef struct {
Thư viện các hàm về đồ thị thông dụng:
NODE *edges[MAXV+1]; /* adjacency info */
int degree[MAXV+1]; /* outdegree of each vertex */
int nvertices; /* number of vertices in graph */
int nedges; /* number of edges in graph */
bool directed; /* is the graph directed? */
} GRAPH;
Tìm kiếm theo chiều rộng ‐ BFS
Cho đồ thị G(V, E), một đỉnh nguồn s
Thuật toán tìm kiếm theo chiều rộng (Breadth‐first
search ‐ BFS) tìm kiếm tất cả các đỉnh mà có thể tới được
từ đỉnh s. Tính toán đường đi ngắn nhất từ đỉnh s đến các
đỉnh có thể tới được từ s.
Để theo dõi quá trình duyệt, ta sử dụng các màu
Màu trắng: đỉnh chưa được thăm
Màu xám: đỉnh đang được thăm
Duyệt đồ thị
Màu đen: đỉnh đã được thăm
•Tìm kiếm theo chiều rộng
•Tìm kiếm theo chiều sâu
Đỉnh màu trắng có thể chuyển sang xám và màu xám có
thể chuyển sang đen.
7
5/5/2011
Tìm kiếm theo chiều rộng ‐ BFS
Tìm kiếm theo chiều rộng ‐ BFS
Để quản lý các đỉnh đang được thăm (màu xám), một
hàng đợi được sử dụng
0
c
b
a
c
b
a
d
g
f
e
d
g
f
A được đưa vào queue
e
Queue
a
0
Đỉnh bắt đầu là a
Queue
Tìm kiếm theo chiều rộng ‐ BFS
Tìm kiếm theo chiều rộng ‐ BFS
2
1
0
1
0
c
c
b
b
a
a
1
d
d
g
g
1
f
f
1
1
2
e
e
•a được lấy khỏi queue
•b được lấy khỏi queue
•Các đỉnh kề a chưa được thăm là b, d,
f được đẩy vào queue
•Các đỉnh kề b chưa được thăm là c,
e được đẩy vào queue
Queue
Queue
b
d
f
d
f
c
e
•a đã được thăm xong, chuyển sang
màu đen
•b đã được thăm xong, chuyển sang
màu đen
1
1
1
1
1
2
2
8
5/5/2011
Tìm kiếm theo chiều rộng ‐ BFS
Tìm kiếm theo chiều rộng ‐ BFS
2
2
1
1
0
0
c
c
b
b
a
a
d
d
1
g
g
1
f
f
1
1
e
e
2
2
•d được lấy khỏi queue
•Không có đỉnh kề d mà chưa
được thăm
•f được lấy khỏi queue
•Không có đỉnh kề f mà chưa được
thăm
Queue
Queue
f
c
e
c
e
•d đã được thăm xong, chuyển
sang màu đen
•f đã được thăm xong, chuyển
sang màu đen
1
2
2
2
2
Tìm kiếm theo chiều rộng ‐ BFS
Tìm kiếm theo chiều rộng ‐ BFS
2
1
2
0
1
0
c
c
b
b
a
a
3
1
d
d
g
g
1
f
f
1
1
2
e
e
2
•c được lấy khỏi queue
•e được lấy khỏi queue
•Không có đỉnh kề c mà chưa được
thăm
•c đã được thăm xong, chuyển
sang màu đen
•Đỉnh kề c mà chưa được thăm là g
được đẩy vào queue
•e đã được thăm xong, chuyển
sang màu đen
Queue
Queue
e
g
2
3
9
5/5/2011
Tìm kiếm theo chiều rộng ‐ BFS
Tìm kiếm theo chiều rộng ‐ BFS
c
b
a
2
1
0
a
c
b
d
g
f
3
e
d
g
1
f
•g được lấy khỏi queue
•Không có đỉnh kề g mà chưa được
thăm
1
e
2
Queue
•g đã được thăm xong, chuyển
sang màu đen
Đồ thị sau khi đã thăm xong các đỉnh bắt đầu từ đỉnh a
Tìm kiếm theo chiều rộng ‐ BFS
Tìm kiếm theo chiều rộng ‐ BFS
Thuật toán BFS, đồ thị G(V, E) và đỉnh bắt đầu là s
Gán tất cả các đỉnh trong G màu trắng
Thêm s và Queue, chuyển màu đỉnh s sang màu xám
Lặp : trong khi queue còn khác rỗng
a
b
d
f
Lấy 1 đỉnh u ra khỏi queue
Với các đỉnh kề v của đỉnh u mà chưa được thăm (màu
trắng) theo thứ tự
c
e
thêm v vào queue
Đổi màu v sang màu xám
Đổi màu u sang màu đen
g
Cây khung thu được khi duyệt đồ thi bắt đầu từ đỉnh a
10
5/5/2011
Tìm kiếm theo chiều rộng ‐ BFS
Tìm kiếm theo chiều sâu ‐ DFS
Thuật toán tìm kiếm theo chiều sâu Depth‐first search (DFS)
Giống BFS nhưng ưu tiên tìm kiếm các đỉnh sâu hơn trước.
Khi một đỉnh được thăm xong, quay lui trở lại để xét tiếp các
đỉnh đang thăm trước đó.
Sử dụng thêm tem thời gian để lưu thời gian thăm các đỉnh
Tem thời gian là 1 số nguyên trong khoảng 1 đến 2|V|
Với mỗi đỉnh v
Độ phức tạp của BFS
O(n2) nếu dùng ma trận kề
O(|V|+|E|) nếu dùng danh sách kề
d[v] f [v]
Tìm kiếm theo chiều sâu ‐ DFS
Tìm kiếm theo chiều sâu ‐ DFS
Ví dụ: cho đồ thị có hướng G(V, E)
c
1|
b
a
c
b
a
d
g
f
d
g
e
f
e
b
a
•Thăm đỉnh ở đầu stack là a
•Trong các đỉnh kề với a chưa được thăm(màu trắng)
ta đẩy đỉnh tiếp theo vào stack (đỉnh b)
a
Đỉnh bắt đầu là a
a
Đẩy a vào stack
Trước sau
11
5/5/2011
Tìm kiếm theo chiều sâu ‐ DFS
Tìm kiếm theo chiều sâu ‐ DFS
3|
2|
2|
c
c
b
b
1|
1|
a
a
d
d
g
g
f
f
e
e
e
c
b
a
c
b
a
c
b
a
b
a
•Đỉnh thăm tiếp theo là c
•Đỉnh kề của c được đẩy vào stack là e
•Đỉnh thăm tiếp theo là đỉnh ở đầy stack (đỉnh b)
•Đỉnh kề với b mà chưa thăm là c và e, ta đẩy c vào stack
Trước sau
Trước sau
Tìm kiếm theo chiều sâu ‐ DFS
Tìm kiếm theo chiều sâu ‐ DFS
3|
3|
2|
2|
c
c
b
b
1|
1|
a
a
d
d
g
e
g
f
f
e
e
4|
4|5
•Đỉnh thăm tiếp theo là e
c
c
b
a
c
b
a
•e không có đỉnh nào kề mà chưa được thăm
nữa nên ta kết thúc thăm e (chuyển màu đen)
•Lấy e ra khỏi stack
b
a
Kết thúc thăm e
Trước sau
12
5/5/2011
Tìm kiếm theo chiều sâu ‐ DFS
Tìm kiếm theo chiều sâu ‐ DFS
3|6
3|6
2|
2|7
c
c
b
b
1|
1|
a
a
d
d
g
g
f
f
e
e
c
b
a
4|5
4|5
b
a
b
a
•
•
Đỉnh thăm tiếp là c, không có đỉnh nào kề c mà chưa
thăm nên ta kết thúc thăm c (chuyển màu đen).
Đẩy c ra khỏi stack
•Đỉnh thăm tiếp là b, không có đỉnh nào kề b mà
chưa thăm nên ta kết thúc thăm b (chuyển màu đen).
•Đẩy b ra khỏi stack
a
Trước sau
Trước sau
Tìm kiếm theo chiều sâu ‐ DFS
Tìm kiếm theo chiều sâu ‐ DFS
3|6
3|6
2|7
2|7
c
c
b
b
1|
1|
a
a
d
d
8|
g
g
f
f
e
e
f
4|5
4|5
d
d
a
d
a
Đỉnh thăm tiếp theo là a, đỉnh kề của a chưa thăm là
d,f. Ta đẩy d vào stack
Đỉnh thăm tiếp theo là d, đỉnh kề của d chưa thăm là
f. Ta đẩy f vào stack
a
a
Trước sau
Trước sau
13
5/5/2011
Tìm kiếm theo chiều sâu ‐ DFS
Tìm kiếm theo chiều sâu ‐ DFS
3|6
3|6
2|7
2|7
c
c
b
b
1|
1|
a
a
d
d
8|
8|
g
g
f
f
9|
9|10
e
e
f
4|5
4|5
d
d
a
d
a
Đỉnh thăm tiếp theo là f, không còn đỉnh nào kề f mà
chưa được thăm. Ta kết thúc thăm f (chuyển f sang màu
đen) và đẩy f ra khỏi stack
Kết thúc thăm f
a
Trước sau
Tìm kiếm theo chiều sâu ‐ DFS
Tìm kiếm theo chiều sâu ‐ DFS
3|6
3|6
2|7
2|7
c
c
b
b
1|
1|12
8|11
a
a
d
d
8|11
g
g
f
f
9|10
9|10
e
e
4|5
4|5
d
Đỉnh thăm tiếp là d, không có đỉnh nào kề b mà chưa
thăm nên ta kết thúc thăm d (chuyển màu đen).
Đẩy d ra khỏi stack
•Đỉnh thăm tiếp là a, không có đỉnh nào kề a mà chưa
thăm nên ta kết thúc thăm a (chuyển màu đen).
•Đẩy a ra khỏi stack
a
a
a
Trước sau
Trước sau
14
5/5/2011
Tìm kiếm theo chiều sâu ‐ DFS
Tìm kiếm theo chiều sâu ‐ DFS
3|6
2|7
a
c
b
1|12
8|11
a
b
d
d
g
f
c
9|10
e
f
4|5
e
Stack đã rỗng, ta dừng thuật toán DFS tại đây!
Các đỉnh được thăm và thời gian thăm trên hình
Cây khung thu được khi duyệt đồ thị bắt đầu từ đỉnh a
Tìm kiếm theo chiều sâu ‐ DFS
Thuật toán DFS, đồ thị G(V, E) và đỉnh bắt đầu là s
Tìm kiếm theo chiều sâu ‐ DFS
Gán tất cả các đỉnh trong G màu trắng
Thêm s và stack, chuyển màu đỉnh s sang màu xám
Lặp: trong khi stack còn khác rỗng
Xét đỉnh u ở đầu stack
Nếu còn tồn tại đỉnh kề với u chưa được thăm (đỉnh có
màu trắng)
Độ phức tạp của DFS
Cỡ O(|V|2) nếu dùng ma trận kề
Cỡ O(|V|+|E|) nếu dùng danh sách kề
Thêm đỉnh kề v đầu tiên của u vào stack
Đổi màu v sang màu xám
Ngược lại :
Đổi màu u sang màu đen
Đẩy u ra khỏi stack
15
5/5/2011
Các loại cạnh trên cây theo DFS/BFS
foward‐edge
Tree‐edge
Ứng dụng của các thuật toán duyệt đồ thị
Back‐edge
Cross‐edge
Ứng dụng của các thuật toán duyệt đồ thị
Bài toán 1. Tìm đường đi ngắn nhất
Bài toán 1. Tìm đường đi ngắn nhất giữa hai đỉnh trên
đồ thị
Trường hợp đồ thị không có trọng số âm:
Thuật toán Dijkstra: Cải tiến từ BFS
Dùng BFS?
Dùng Priority queue lưu trữ các đỉnh theo quãng đường
Dùng DFS?
Đồ thị có trọng số âm
Dijkstra không thực hiện được?
Trường hợp không có chu trình âm
Thuật toán Ford Bellman
Đồ thị có chu trình âm
Thuật toán Floyd Warshall
16
5/5/2011
Ứng dụng của các thuật toán duyệt đồ thị
Bài toán 2. Thành phần liên thông
Bài toán 2. Thành phần liên thông – connected components
Thành phần liên thông của 1 đồ thị vô hướng là tập đỉnh lớn
nhất mà luôn tồn tại đường đi giữa 2 đỉnh bất kỳ trong đó
Kiểm tra đồ thị liên thông
Thực hiện DFS hoặc BFS
Tất cả các đỉnh đều được thăm liên thông
1
Tìm kiếm thành phần liên thông
Thực hiện DFS hoặc BFS
Đưa ra tập đỉnh liên thông lớn nhất
2
7
9
4
8
6
3
5
Ứng dụng của các thuật toán duyệt đồ thị
Bài toán 3. Bi‐coloring
Bài toán 3. Bi‐coloring graphs – tô màu các đỉnh trên đồ
thị bằng 2 màu. Kiểm tra xem có thể tô màu các đỉnh trên
đồ thị chỉ bằng 2 màu sao cho 2 đỉnh của mỗi cạnh đều có
màu khác nhau
Kiểm tra bằng cách duyệt đồ thị
Thực hiện BFS để đánh màu các đỉnh
Hai mút của 1 cạnh phải có 2 màu khác nhau
Nếu tồn tại 1 cạnh mà 2 mút có cùng màu không tô được
bằng 2 màu
1
1
2
2
Bài toán tô màu đồ thị tổng quát
4
Dùng số màu ít nhất để tô cho các đỉnh sao cho không cạnh
nào có 2 mút trùng màu
Là bài toán thuộc lớp NP‐Khó
Không có thuật toán hiệu quả để giải trong trường hợp tổng
4
6
6
3
3
5
5
quát
17
5/5/2011
Ứng dụng của các thuật toán duyệt đồ thị
Bài toán 4. Tìm chu trình
Bài toán 4. Tìm chu trình trên đồ thị
Phát hiện chu trình bằng Back Edge
Duyệt đồ thị bằng DFS
Tìm cạnh ngược – back edge
Cạnh ngược – back edge: cạnh từ nút con cháu đến nút tổ
tiên (không phải nút cha trực tiếp của nó)
Ứng dụng của các thuật toán duyệt đồ thị
Bài toán 5. Articulation vertex
Bài toán 5. Tìm đỉnh khớp (đỉnh cắt)– articulation vertex
(cut node). Đỉnh mà nếu bị gỡ bỏ sẽ làm đồ thị liên thông
bị tách thành 2 phần
Thực hiện brute force: duyệt tất cả các đỉnh trên cây để
tìm đỉnh cắt
Thời gian thực hiện lớn ꢕꢄ|ꢎ|ꢄ ꢎ ꢚ |ꢏ|ꢇꢇ
Thực hiện tìm trên cây khung thu được sau khi DFS
DFS trên đồ thị vô hướng chỉ thu được tree edge và back edge
Nút lá trên cây khung thu được không phải là đỉnh cắt
Thời gian thực hiện ꢕꢄ ꢎ ꢚ |ꢏ|ꢇ
Các loại đỉnh cắt – articulation vertex có thể:
Nút gốc có nhiều hơn 1 con
Nút mà các nút con cháu của nó không có cạnh ngược đến nút
tổ tiên
18
5/5/2011
Ứng dụng của các thuật toán duyệt đồ thị
Bài toán 6. Topological sorting
Bài toán 6. Sắp xếp topo – topological sorting: cho một đồ thị
vô hướng không có chu trình – DAG, hãy đưa ra một thứ tự
các đỉnh trong đó nếu có cạnh (u,v) thì u phải đứng trước v
Dùng DFS:
Nếu có cạnh (u,v) thì thời điểm kết thúc thăm u bao giờ cũng
lớn hơn thời điểm kết thúc thăm v
Thực hiện DFS trên toàn bộ đồ thị và đưa ra các đỉnh theo thứ
tự thời điểm kết thúc thăm giảm dần
1
2
Dùng BFS
Đỉnh mà không có cạnh tới phải đứng đầu trong danh sách
topo
4
6
Tìm đỉnh không có cạnh tới, đưa đỉnh này vào danh sách topo
sau đó xoá các cạnh xuất phát từ đỉnh đó
3
Một thứ tự topo của đồ thị là
5, 6, 1, 2, 3, 4
5
Ứng dụng của các thuật toán duyệt đồ thị
Bài toán 7. strongly connected component
Bài toán 7. Thành phần liên thông mạnh – strongly connected
component. Đó là một phần của một đồ thị có hướng trong đó
luôn tồn tại đường có hướng giữa hai cặp đỉnh bất kỳ.
Kiểm tra đồ thị là strongly connected
Thực hiện DFS từ 1 đỉnh v tuỳ ý
Đổi hướng các đỉnh trên đồ thị cũ và thực hiện DFS lại với đỉnh v
Bài toán chia đồ thị thành các tập con trong đó mỗi tập con
là một thành phần liên thông mạnh
Không có một đỉnh nào là cùng thuộc 2 tập con liên thông mạnh
trên đồ thị
1
2
Thuật toán
4
6
Kosaraju: cần 2 lần DFS trên đồ thị
Tarjan
Gabow
3
1 Lần DFS
5
Thời gian ꢕꢄ ꢎ ꢚ |ꢏ|ꢇ
19
5/5/2011
Ứng dụng của các thuật toán duyệt đồ thị
Bài 8. Minimum spanning tree
Bài toán 8. Cây khung có trọng số nhỏ nhất trên đồ thị ‐
minimum spanning tree (MST)
Thuật toán PRIM
Đồ thị ꢌꢄꢎ, ꢏꢇ, cây khung ꢛꢄꢎꢍ, ꢏ′ꢇ (ꢎꢍ ꢉ ꢎ khi kết thúc)
Khởi tạo
Cây khung: là cây chứa mà kết nối tất cả các đỉnh của đồ thị
ꢏꢍ ꢉ ∅, ꢎꢍ ꢉ ∅
ꢜꢝꢞꢟ ꢉ 0
ꢎꢍ ꢉ ꢎꢍ ∪ ꢠꢀꢡ (ꢀ là đỉnh bất kỳ trên ꢌꢄꢎ, ꢏꢇ)
Lặp cho tới khi ꢎꢍ ꢉ ꢎ
A
1
A
1
3
B
4
7
F
4
D
3
B
7
5
F
A
D
D
1
E
Tìm cạnh ꢔ, ꢀ , ꢔ ∈ ꢎꢍ, ꢀ ∈ ꢎ ∖ ꢎ′ có trọng số nhỏ nhất
ꢏꢍ ꢉ ꢏꢍ ∪ ꢠꢄꢔ, ꢀꢇꢡ
ꢎꢍ ꢉ ꢎꢍ ∪ ꢠꢀꢡ
ꢜꢝꢞꢟ ꢉ ꢜꢝꢞꢟ ꢚ ꢢꢗꢈꢘꢣꢟꢄꢔ, ꢀꢇ
1
2
6
5
3
C
3
B
E
1
F
Cây khung
C
2
3
(spanning tree)
Cost = 17
G(V, E)
E
1
MST
Cost = 10
C
Bài 8. Minimum spanning tree
Bài 8. Minimum spanning tree
Thuật toán Kruskal
PRIM
Đồ thị ꢌꢄꢎ, ꢏꢇ, cây khung ꢛꢄꢎꢍ, ꢏ′ꢇ (ꢎꢍ ꢉ ꢎ khi kết thúc)
Khởi tạo
Lặp |ꢎ| lần, mỗi lần phải duyệt |ꢏ| cạnh ? Thời gian ꢕꢄ ꢎ ∗ |ꢏ|ꢇ?
Mỗi lần lặp chỉ xét thêm ꢥ |ꢎ| ꢋ 1 cạnh nhỏ nhất ꢕꢄ|ꢎ|ꢃꢇ
Sắp xếp các cạnh theo thứ tự tăng dần trọng số (priority queue Q)
ꢏꢍ ꢉ ∅, ꢎꢍ ꢉ ∅
Cài đặt dùng hàng đợi ưu tiên phức tạp giúp giảm thời gian thực
hiện xuống ꢕꢄ ꢏ ꢚ |ꢎ|log |ꢎ|ꢇ
Kruskal
ꢜꢝꢞꢟ ꢉ 0, ꢜꢝꢔꢑꢟ ꢉ 0
Sắp xếp |ꢏ| cạnh mất thời gian ꢕꢄ|ꢏ|log |ꢏ|ꢇ
Lặp cho tới khi Cꢝꢔꢑꢟ ꢉ ꢏ ꢋ 1
Lấy cạnh ꢄꢔ, ꢀꢇ tiếp theo trong Q
Lặp |ꢎ| ꢋ 1 lần, mỗi lần thêm cạnh và kiểm tra chu trình mất thời
gian thực hiện cỡ V ∗ |ꢏ| nên thời gian Kruskal cỡ
ꢕ ꢎ ∗ ꢏ ꢚ ꢏ log ꢏ
Nếu thêm ꢄꢔ, ꢀꢇ vào ꢛ mà không tạo thành chu trình
ꢎꢍ ꢉ ꢎꢍ ∪ ꢠꢔ, ꢀꢡ; ꢏꢍ ꢉ ꢏꢍ ∪ ꢔ, ꢀ
Cải thiện thao tác kiểm tra chu trình trong Kruskal, dùng cấu trúc
các tập độc lập – Union data structure
ꢜꢝꢞꢟ ꢉ ꢜꢝꢞꢟ ꢚ ꢢꢗꢈꢘꢣꢟ ꢔ, ꢀ ; ꢜꢝꢔꢑꢟ ꢉ ꢤꢝꢔꢑꢟ ꢚ 1
Ngược lại, loại bỏ ꢄꢔ, ꢀꢇ khỏi Q
20
Tải về để xem bản đầy đủ
21 trang
15580
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 7: Đồ thị - Nguyễn Duy Hiệp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_phan_1_gioi_thieu_v.pdf
