Bài giảng Thuật toán ứng dụng - Chương 6, Phần 2: Graphs - Phạm Quang Dũng
Nội dung
Đồ thị và cá c thuật ngữ liên quan
Tì m kiếm theo chiều sâ u
Tì m kiếm theo chiều rộng
Chu trì nh Euler
Thuật toá n Dijkstra sử dụng hàng đợi ưu tiên
Thuật toá n Kruskal sử dụng disjoint-set structure
Exercises
2
Đồ thị
Đối tượng toá n học bao gồm cá c đỉnh (node) và cá c liên kết
giữa cá c đỉnh (cạnh, cung)
Đồ thị G = (V,E), trong đó V là tập đỉnh, E là tập cạnh
(cung)
(u,v) E, chúng ta nó i u kề với v
6
2
6
3
2
4
1
5
1
5
3
4
Undirected graph
V = {1, 2, 3, 4, 5, 6}
Directed graph
V = {1, 2, 3, 4, 5, 6}
E = {(1, 3), (1,6), (2, 4), (2, 5),
E = {(1, 3), (1,6), (2, 4), (2, 5),
3
(2, 6), (3, 4), (3, 6), (4, 5)}
(6, 2), (3, 4), (6, 3), (4, 5)}
Đồ thị
Bậc của một đỉnh là số đỉnh kề với nó
deg(v) = #{u | (u, v) E}
Bá n bậc vào (bá n bậc ra) của một đỉnh là số cung đi vào (đi ra) khỏi
đỉnh đó trên đồ thị có hướng:
deg-(v) = #{u | (u, v) E}, deg+(v) = #{u | (v, u) E}
6
3
2
4
6
3
2
4
1
5
1
5
Undirected graph
deg(1) = 2, deg(6) = 3
Directed graph
deg-(1) = 0, deg+(1) = 2
4
Đồ thị
Cho đồ thị G=(V, E) và 2 đỉnh s, t V, một đường đi từ s
đến t trên G là chuỗi s = x0, x1, …, xk = t trong đó (xi,
xi+1)E, i = 0, 1, …, k-1
6
2
4
6
2
4
1
5
1
5
3
3
Path from 1 to 5:
1, 3, 4, 5
Path from 1 to 5:
1, 3, 4, 5
1, 6, 2, 5
1, 6, 4, 5
5
Đồ thị đặc biệt
1
2
3
1
1
4
6
2
3
3
2
5
4
5
4
Đồ thị đầy đủ
Đồ thị hai phí a
Đồ thị phẳng
6
Đồ thị
Ma trận kề
Ma trận trọng số
4
6
2
4
6
2
3
6
1
5
1
5
5
9
2
7
8
3
3
4
1 2 3 4 5 6
0 0 1 0 0 1
1 2 3 4 5 6
0 0 7 0 0 3
1
1
0 0 0 1 1 1
1 0 0 1 0 1
0 1 1 0 1 0
0 1 0 1 0 0
1 1 1 0 0 0
0 0 0 9 6 4
7 0 0 8 0 5
0 9 8 0 2 0
0 6 0 4 0 0
3 4 5 0 0 0
2
2
3
4
3
4
5
6
5
6
7
Biểu diễn đồ thị
Danh sá ch kề
Với mỗi v V, A(v) là tập cá c bộ (v, u, w) trong đó
w là trọng số cung (v, u)
4
6
3
2
3
7
A(1) = {(1, 6, 3), (1, 3, 7)}
A(2) = {(2, 4, 9), (2, 5, 6)}
A(3) = {(3, 4, 8)}
6
1
5
5
9
2
8
4
A(4) = {(4, 5, 2)}
A(5) = {}
A(6) = {(6, 3, 5), (6, 2, 4)}
8
Duyệt đồ thị
Thăm cá c đỉnh của đồ thị theo một thứ tự nào đó
Mỗi đỉnh thăm đúng 1 lần
Có 2 phương phá p chí nh
Duyệt theo chiều sâ u: Depth-First Search (DFS)
Duyệt theo chiều rộng: Breadth-First Search (BFS)
9
Depth-First Search (DFS)
DFS(u): DFS bắt đầu thăm từ đỉnh u
Nếu tồn tại một đỉnh v trong danh sá ch kề của u mà chưa
được thăm → tiền hành thăm v và gọi DFS(v)
Nếu tất cả cá c đỉnh kề với u đã được thăm → DFS quay
lui trở lại đỉnh x từ đó thuật toá n thăm u và tiến hành thăm
cá c đỉnh khá c kề với x (gọi DFS(x)) mà chưa được thăm.
Lúc này, đỉnh u được gọi là đã duyệt xong
10
Depth-First Search (DFS)
Cá c thô ng tin liên quan đến mỗi đỉnh v
p(v): là đỉnh mà từ đó, DFS thăm đỉnh v
d(v): thời điểm đỉnh v được thăm nhưng chưa duyệt xong
f(v): thời điểm đỉnh v đã duyệt xong
color(v)
WHITE: chưa thăm
GRAY: đã được thăm nhưng chưa duyệt xong
BLACK: đã duyệt xong
11
Depth First Search - DFS
DFS(u) {
DFS() {
t = t + 1;
d(u) = t;
color(u) = GRAY;
foreach (node u of V) {
color(u) = WHITE;
p(u) = NIL;
foreach(adjacent node v to u)
{
}
if(color(v) = WHITE) {
t = 0;
p(v) = u;
DFS(v);
foreach(node u of V) {
if(color(u) = WHITE) {
}
}
DFS(u);
t = t + 1;
f(u) = t;
color(u) = BLACK;
}
}
}
}
12
Depth First Search - DFS
6
3
2
Node 1
2
3
4
5
6
7
d
f
1
5
4
p
-
-
-
-
-
-
-
color
W
W
W
W W W W
7
13
Depth First Search - DFS
DFS(1)
1
Node 1
2
3
4
5
6
7
d
1
f
p
-
-
-
-
-
-
-
color
G
W
W
W W W W
6
3
2
1
5
4
7
14
Depth First Search - DFS
DFS(1)
1
Node 1
2
3
4
5
6
7
d
1
2
f
3
p
-
-
1
-
-
-
-
color
G
W
G
W W W W
6
3
2
1
5
4
7
15
Depth First Search - DFS
DFS(1)
1
Node 1
2
3
4
5
6
7
d
1
2
3
f
3
4
p
-
-
1
3
-
-
-
color
G
W
G
G
W W W
6
3
2
4
1
5
7
16
Depth First Search - DFS
DFS(1)
1
Node 1
2
3
4
5
6
7
d
1
2
3
4
5
f
3
4
p
-
-
1
3
4
-
-
color
G
W
G
G
G
W W
6
3
2
4
1
5
7
17
Depth First Search - DFS
DFS(1)
1
Node 1
2
3
4
5
4
5
4
B
6
7
d
1
2
3
5
f
3
4
p
-
-
1
3
-
-
color
G
W
G
G
W W
6
3
2
4
1
5
7
18
Depth First Search - DFS
DFS(1)
1
Node 1
2
3
4
5
4
5
4
B
6
7
d
1
2
3
6
5
f
3
4
p
-
-
1
3
-
4
color
G
W
G
G
W G
7
6
3
2
4
1
5
7
19
Depth First Search - DFS
DFS(1)
1
Node 1
2
3
4
5
4
5
4
B
6
7
6
7
4
d
1
2
3
5
f
3
4
p
-
-
1
3
-
color
G
W
G
G
W B
7
6
3
2
4
1
5
7
20
Tải về để xem bản đầy đủ
141 trang
17100
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thuật toán ứng dụng - Chương 6, Phần 2: Graphs - Phạm Quang Dũng", để 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_thuat_toan_ung_dung_chuong_6_phan_2_graphs_pham_qu.pdf
