GIỚI THIỆU
• Đồ thị là một cấu trúc dữ liệu trừu tượng dựa trên các khái niệm
toán học về đồ thị.
• Đồ thị được xem là tổng quát hóa của cấu trúc cây. Tuy nhiên, đồ thị có mối quan hệ phức tạp hơn là quan hệ cha-con trong cấu trúc cây.
• Đồ thị được sử dụng trong nhiều ứng dụng như cây gia phả,
mạng quản lý chuyến bay v.v…
3
KHOA CÔNG NGHỆ THÔNG TIN
GIỚI THIỆU
• Một đồ thị G là một tập hợp không có thứ tự (V, E), trong đó
V : là các đỉnh của đồ thị
E : là các cạnh (cung) biểu diễn mối quan hệ giữa các đỉnh
V(G) = {A, B, C, D, E}
A B C
E(G) = {(A, B), (A, D), (B, C}, (B, D), (C, E), (D, E)}
D
E
4
KHOA CÔNG NGHỆ THÔNG TIN
GIỚI THIỆU
• Một đồ thị G có thể có hướng hoặc vô hướng.
• Nếu đồ thị có hướng thì cạnh nối hai đỉnh có mũi tên đại diện
cho hướng nối.
Đồ thị có hướng
Đồ thị vô hướng
D
E
D
E
A B C C A B
5
KHOA CÔNG NGHỆ THÔNG TIN
BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. SỬ DỤNG MA TRẬN KỀ
• Hai đỉnh kề nhau nếu có cạnh nối giữa chúng
• Ta dùng một ma trận với dòng, cột biểu diễn cho các đỉnh của
đồ thị.
• Biểu diễn cạnh trên ma trận kề
Nếu đỉnh i kề đỉnh j
1
𝑎𝑖𝑗 =
0
Ngược lại
6
KHOA CÔNG NGHỆ THÔNG TIN
BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. SỬ DỤNG MA TRẬN KỀ
C
B
C
A
B
A
A B C D E
A B C D E
A
0
1
0
1
0
0
A
0
1
1
0
B
1
0
1
1
0
0
B
0
0
1
0
C 0
1
0
0
1
0
C 0
1
0
0
D 1
1
0
0
1
0
D 0
0
0
1
E
0
0
1
1
0
1
E
0
0
0
0
D E D E
7
KHOA CÔNG NGHỆ THÔNG TIN
BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. SỬ DỤNG MA TRẬN KỀ
C
A
B
5 4
2
7
Đồ thị có trọng số là đồ thị mà có gán dữ liệu trên mỗi cạnh.
1
3
A B C D E
D E
Biểu diễn đồ thị có trọng số
A
0
4
0
0
2
B
0
0
0
0
7
C 0
5
0
0
0
D 0
0
3
0
0
E
0
0
0
1
0
8
KHOA CÔNG NGHỆ THÔNG TIN
BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. SỬ DỤNG MA TRẬN KỀ
A
B
C
5 4
2
7
• Đối với đồ thị đơn (không có vòng), ma trận kề có đường chéo chính mang giá trị 0
1
D E
• Ma trận kề đồ thị vô hướng thì đối
3
xứng
A B C D E
4
A
0
0
2
0
• Bộ nhớ của ma trận kề là O(n2), n là
0
B
0
0
7
0
số đỉnh của đồ thị.
5
C 0
0
0
0
0
D 0
0
0
3
0
E
0
1
0
0
9
KHOA CÔNG NGHỆ THÔNG TIN
BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 2. SỬ DỤNG DANH SÁCH KỀ
• Danh sách kề gồm các đỉnh của đồ thị V(G).
• Mỗi đỉnh vi là một danh sách liên kết lưu trữ những đỉnh vj , vj+1,
… nối tới vi
• Thường dùng để lưu đồ thị nhỏ và vừa.
• Biểu diễn đồ thị thưa (có ít cạnh nối) trong bộ nhớ máy tính.
10
KHOA CÔNG NGHỆ THÔNG TIN
BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 2. SỬ DỤNG DANH SÁCH KỀ
• Danh sách kề biểu diễn đồ thị vô hướng.
NULL
B
D
A
B
NULL
A
C
NULL
B
E
C
A B C
NULL
D
A
B
E
NULL
C
D
D E
11
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG
• Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng.
Xuất phát từ đỉnh A
C A B
D E
12
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG
• Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng.
B1: Xuất phát từ đỉnh A B2: Đi qua đỉnh B, D
B A
D
13
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG
• Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng.
B1: Xuất phát từ đỉnh A B2: Đi qua đỉnh B, D B3: Xuất phát từ đỉnh B B4: Đi qua đỉnh C
A B C
D
14
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG
• Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng.
A B C
B1: Xuất phát từ đỉnh A B2: Đi qua đỉnh B, D B3: Xuất phát từ đỉnh B B4: Đi qua đỉnh C B5: Xuất phát từ đỉnh D
D
15
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG
• Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng.
B1: Xuất phát từ đỉnh A
B2: Đi qua đỉnh B, D
B3: Xuất phát từ đỉnh B
A B C
B4: Đi qua đỉnh C
B5: Xuất phát từ đỉnh D
B6: Đi qua đỉnh E
Dừng thuật toán
D E
16
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG
GIẢI THUẬT : Duyệt theo chiều rộng (BFS) procedure BFS(G: đồ thị với các đỉnh v1, v2, …, vn) T := cây chỉ chứa một đỉnh ban đầu v1 L := danh sách rỗng dùng để chứa các đỉnh đã đi qua Đặt đỉnh v1 vào danh sách L while L không rỗng
remove đỉnh v1 từ L for mỗi đỉnh kề w với đỉnh v1 do
if
w không có trong L and không có trong T then
w vào L
add add w and cạnh {v1, w} vào T
17
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG
Độ phức tạp không gian
• Tất cả các đỉnh tại mức đang xét sẽ được lưu cho đến khi các
đỉnh kề được đi qua.
• Độ phức tạp không gian tỉ lệ thuận với số đỉnh ở mức sâu nhất
của đồ thị.
• Cho đồ thị có b là số đỉnh kề của mỗi đỉnh và chiều sâu d. Độ
phức tạp không gian là số đỉnh ở mức sâu nhất O(bd).
18
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG
Độ phức tạp thời gian
Trường hợp xấu nhất, BFS phải duyệt tất cả đường đi tới các đỉnh. Độ phức tạp thời gian xấp xỉ O(bd)
Tính đầy đủ
BFS có tính đầy đủ vì nó sẽ tìm tất cả các đỉnh không phân biệt loại đồ thị (vô hướng, có hướng, có trọng số…).
19
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 2. DUYỆT THEO CHIỀU SÂU
Duyệt theo chiều sâu (Depth-First Search) đồ thị vô hướng.
Xuất phát từ đỉnh A
C A B
D E
20
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 2. DUYỆT THEO CHIỀU SÂU
Duyệt theo chiều sâu (Depth-First Search) đồ thị vô hướng.
B1: Xuất phát từ đỉnh A
B2: Đi qua đỉnh B
A B
21
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 2. DUYỆT THEO CHIỀU SÂU
Duyệt theo chiều sâu (Depth-First Search) đồ thị vô hướng.
B1: Xuất phát từ đỉnh A
B2: Đi qua đỉnh B
A B C
B3: Đi qua đỉnh C
22
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 2. DUYỆT THEO CHIỀU SÂU
Duyệt theo chiều sâu (Depth-First Search) đồ thị vô hướng.
B1: Xuất phát từ đỉnh A
B2: Đi qua đỉnh B
A C B
B3: Đi qua đỉnh C
E
B4: Đi qua E
23
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 2. DUYỆT THEO CHIỀU SÂU
Duyệt theo chiều sâu (Depth-First Search) đồ thị vô hướng.
B1: Xuất phát từ đỉnh A
B2: Đi qua đỉnh B
A B C
B3: Đi qua đỉnh C
D E
B4: Đi qua E
B5: Đi qua D
24
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 2. DUYỆT THEO CHIỀU SÂU
THUẬT TOÁN : Duyệt theo chiều sâu (DFS) procedure DFS(G: đồ thị với các đỉnh v1, v2, …, vn)
T := cây chứa một đỉnh ban đầu v1 visit(v1)
procedure visit(v: đỉnh của G) for mỗi đỉnh w kề v và không trong T do add đỉnh w và cạnh {v, w} vào T visit(w)
25
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN DUYỆT ĐỒ THỊ 2. DUYỆT THEO CHIỀU SÂU
Độ phức tạp không gian
Độ phức tạp không gian của DFS thấp hơn BFS
Độ phức tạp thời gian
Tỉ lệ thuận với số đỉnh và số cạnh trong đồ thị đã được duyệt. Độ phức tạp thời gian là O(|V| + |E|).
Tính đầy đủ
DFS có tính đầy đủ vì nó sẽ tìm tất cả các đỉnh không phân biệt loại đồ thị (vô hướng, có hướng, có trọng số…).
26
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 1. CÂY KHUNG TỐI THIỂU
Giới thiệu cây khung tối thiểu
• Cây khung của đồ thị G là cây kết nối tất cả các đỉnh.
• Cây khung tối thiểu là cây có tổng trọng số của các cạnh nhỏ nhất.
3
3
3
A
B
A
B
A
B
5
7
7
6
4
4
C
D
C
D
C
D
2
2
2
Tổng chi phí = 12
Tổng chi phí = 9
27
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 2. THUẬT TOÁN PRIM
3
A
B
B1: Xuất phát đỉnh T: {A}
5
7
6
4
C
D
2
28
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 2. THUẬT TOÁN PRIM
3
A
B
B1: Xuất phát đỉnh T:= {A}
B2: chọn đỉnh B vì có trọng số nhỏ
7
4
trong những đỉnh kề với A
C
D
29
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 2. THUẬT TOÁN PRIM
3
A
B
B1: Xuất phát đỉnh T:= {A}
5
B2: chọn đỉnh B vì có trọng số nhỏ
7
6
4
trong những đỉnh kề với A
C
D
B3: Từ tập {A, B} xét các đỉnh kề
Với chúng {C, D}, chọn đỉnh C
30
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 2. THUẬT TOÁN PRIM
3
A
B
B1: Xuất phát đỉnh T: = {A}
7
B2: chọn đỉnh B vì có trọng số nhỏ
6
4
trong những đỉnh kề với A
C
D
2
B3: Từ tập {A, B} xét các đỉnh kề
Với chúng {C, D}, chọn đỉnh C
B4: Chọn D
31
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 2. THUẬT TOÁN PRIM
GIẢI THUẬT : PRIM procedure Prim(G: đồ thị gồm các đỉnh v1, v2, …, vn) T := {v1} for i := 0 to n – 2 do
e := chọn cạnh có trọng số nhỏ nhất nối tới
đỉnh trong T và không tạo chu trình trong T
T := T U e
return T
32
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 3. THUẬT TOÁN KRUSKAL
3
A
B
B1: Chọn cạnh có trọng số nhỏ nhất CD = 2 và thêm vào T := {(C, D)}
5
7
6
4
C
D
2
33
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 3. THUẬT TOÁN KRUSKAL
3
A
B
B1 : Chọn cạnh có trọng số nhỏ nhất
5
CD = 2 và thêm vào T := {(C, D)}
7
6
4
B2 : Chọn cạnh có trọng số nhỏ nhất
C
D
AB = 3 và thêm vào T := {(C,D), (A,B)}
2
34
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 3. THUẬT TOÁN KRUSKAL
3
A
B
B1 : Chọn cạnh có trọng số nhỏ nhất
5
CD = 2 và thêm vào T := {(C, D)}
7
6
4
B2 : Chọn cạnh có trọng số nhỏ nhất
C
D
AB = 3 và thêm vào T := {(C,D), (A,B)}
2
B3 : Chọn cạnh có trọng số nhỏ nhất
AC = 4
Dừng vì cây liên thông và qua tất cả
các đỉnh
35
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 3. THUẬT TOÁN KRUSKAL
THUẬT TOÁN : KRUSKAL procedure Kruskal(G: đồ thị gồm các đỉnh v1, v2, …, vn) T := ∅ for i := 1 to n – 1 do
e := chọn bất kỳ cạnh trong G có trọng số nhỏ
nhất nhưng không tạo chu trình trong T
T := T U e
return T
36
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
• Tìm đường đi ngắn nhất giữa 2 đỉnh trong một đồ thị
• Chỉ thực hiện trên trọng số dương
• Áp dụng cho đồ thị vô hướng và có hướng
37
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
b
Tìm đường ngắn nhất
2
c 3
từ đỉnh a đến đỉnh d
4
3 a d
1 2
e 3 f
38
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
Khởi động
∞ b
∞ c
d(a) = 0
2
3
4
d(b) = ∞
∞
3 a 0 d
d(f) = ∞
1
d(c) = ∞
2
3
d(e) = ∞
d(d) = ∞
e ∞ f ∞
39
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
Bắt đầu đỉnh a
4(𝑎) b
∞ c
3
d(a) = 0
2
4
3 a 0
d(b) = min(d(b), d a + w a, b ) = min(∞, 0 + 4) = 4
d ∞
d(f) = min d f , d a + w a, f = min ∞, 0 + 2 = 2
1 2
3
e ∞ f 2 (a)
d(c) = ∞
d(e) = ∞
d(d) = ∞
40
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
Vì d(f) < d(b) , bắt đầu đỉnh f
4(𝑎) b
∞ c
3
d(a) = 0 (đã đi qua)
2
4
d(b) = 4
3 a 0
d(f) = 2
d ∞
d(c) = ∞
1 2
3
d(e) = min d e , d f + w f, e = min(∞, 2 + 3) = 5
e ∞
f 2 (a)
d(d) = ∞
41
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
Vì d(b) < d(e), bắt đầu đỉnh b
4(𝑎) b
∞ c
d(a) = 0 (đã đi qua)
2
3
d(b) = 4
4
d(f) = 2 (đã đi qua)
3 a 0
d ∞
d(c)= min d c , 𝑑 𝑏 + 𝑤 𝑏, 𝑐 = min ∞, 4 + 3 = 7
1 2
3
e 5 (f)
f 2 (a)
d(e) = min(5, d(b)+w(b, e)) = min(5, 4 + 3) = 5
d(d) = ∞
42
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
Vì d(e) < d(c) , bắt đầu đỉnh e
4(𝑎) b
7 (b) c
3
d(a) = 0 (đã đi qua)
2
4
d(b) = 4 (đã đi qua)
3 a 0
d(f) = 2 (đã đi qua)
d ∞
d(c) = 7
1 2
d(e) = 5
3
e 5 (f)
d(d) = min ∞, 𝑑 𝑒 + 𝑤 𝑒, 𝑑 = min ∞, 5 + 1 = 6
f 2 (a)
43
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
Vì d(d) < d(c), bắt đầu đỉnh d
4(𝑎) b
7 (b) c
3
d(a) = 0 (đã đi qua)
2
4
d(b) = 4 (đã đi qua)
3 a 0
d 6, (𝑒)
d(f) = 2 (đã đi qua)
d(c) = min(7, d(d) + w(d, c))= min(7, 6 + 2) = 7
1 2
3
e 5 (f)
d(e) = 5 (đã đi qua)
f 2 (a)
d(d) = 6
44
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
d(a) = 0 (đã đi qua)
4(𝑎) b
7 (b) c
3
d(b) = 4 (đã đi qua)
2
4
d(f) = 2 (đã đi qua)
3 a 0
d 6, (𝑒)
d(c) = 7
d(e) = 5 (đã đi qua)
1 2
d(d) = 6 (đã đi qua)
3
e 5 (f)
Dừng
f 2 (a)
45
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
Ta có các đường đi ngắn nhất
4(𝑎) b
7 (b) c
2
3
a b = 4
4
a b c = 7
3 a 0
d 6, (𝑒)
a f = 2
1 2
a f e d = 6
3
e 5 (f)
a f e = 5
f 2 (a)
46
KHOA CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT 4. THUẬT TOÁN DIJKSTRA
THUẬT TOÁN DIJKSTRA procedure DIJKSTRA (G, w, s, d) d(s) := 0, T := V for mỗi v thuộc V do d(v) := ∞ while T ≠ ∅ do
Tìm u thuộc T sao cho d(u) nhỏ nhất T := T \ {u} for v thuộc tập đỉnh kề v do
d(v) := min(d(v), d(u) + w(u, v))
return d(v)
47
KHOA CÔNG NGHỆ THÔNG TIN
BÀI TẬP
1. Dùng DFS và BFS duyệt các đỉnh của đồ thị sau. Trình bày
từng bước
G
A
B
E
F
C
D
H
48
KHOA CÔNG NGHỆ THÔNG TIN
BÀI TẬP
2. Dùng Prim, Kruskal và Dijkstra cho đồ thị sau. Trình bày từng bước cụ thể.
G
2
2
2
A
B
3
2
3
3
E
F
6
2
C
D
4
4
5
3
1
H
49
KHOA CÔNG NGHỆ THÔNG TIN
BÀI TẬP
3. Cho ma trận sau
A
B
C
D
E
F
0
2
3
0
0
0
A
a) Vẽ đồ thị
2
0
0
5
2
0
B
b) Dùng DFS, BFS
3
0
0
0
5
0
C
c) Dùng Prim, Kruskal
0
5
0
0
1
2
D
d) Dùng Dijkstra từ đỉnh a đến f
0
2
5
1
0
4
E
0
0
0
2
4
0
F
