Bài giảng "Cấu trúc dữ liệu và giải thuật: Đồ thị" cung cấp cho người học các kiến thức: Đồ thị và biểu diễn đồ thị, duyệt đồ thị, sắp xếp topo, tìm đường đi ngắn nhất. Mời các bạn cùng tham khảo nội dung chi tiết.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Đồ thị - Phan Mạnh Hiển (2020)
- Đồ thị
(Graphs)
Nguyễn Mạnh Hiển
hiennm@tlu.edu.vn
- Nội dung
• Đồ thị và biểu diễn đồ thị
• Duyệt đồ thị
• Sắp xếp topo
• Tìm đường đi ngắn nhất
- Đồ thị và biểu diễn đồ thị
- Đồ thị
v1 v2 v3
• Đồ thị G = (V, E) bao gồm một
tập đỉnh V và một tập cạnh E
• Mỗi cạnh là một cặp (v, w) v4 v5 v6
trong đó v, w V
• Đồ thị không có hướng: v7
− Các cạnh không có thứ tự v8
− Cạnh (v, w) giống như cạnh (w, v)
• Đồ thị không có hướng được vẽ bằng
các nút cho các đỉnh và các đoạn thẳng
cho các cạnh
- Đồ thị có hướng
v1 v2 v3
• Trong đồ thị có hướng, E là
một tập các cặp có thứ tự,
nhưng không nhất thiết là v4 v5 v6
tập đối xứng, tức là nếu cạnh
(v, w) có mặt thì cạnh (w, v) v7
có thể vắng mặt v8
• Đồ thị có hướng được vẽ bằng
các nút cho các đỉnh và các mũi
tên cho các cạnh
- Đường đi và trọng số
• Đường đi là một dãy đỉnh w1, w2, …, v2 v3
v1
wn, trong đó có một cạnh giữa hai -2
3 5 2
đỉnh liên tiếp wi và wi+1
• Chiều dài của đường đi có n đỉnh v4 v5 v6
bằng n – 1 (số cạnh) -1
• Đường đi là đơn giản nếu tất cả các v7 1 4
đỉnh trên đường đi khác nhau (ngoại
trừ đỉnh đầu và đỉnh cuối có thể trùng v8
nhau)
• Các cạnh có thể có trọng số (hay chi
phí) kèm theo
• Chi phí của đường đi bằng tổng trọng
số của các cạnh trên đường đi đó
- Chu trình
v2 v3 v1 v2 v3
v1
v4 v4 v5 v6
v5 v6
v7 v7
v8 v8
• Chu trình là đường đi w1, w2, …, wn = w1, trong đó đỉnh đầu và đỉnh
cuối trùng nhau
− Chu trình đơn giản nếu đường đi đó đơn giản
• Trong hình vẽ bên trên: v2, v8, v6, v3, v5, v2 là một chu trình (đơn
giản) trong đồ thị không có hướng, nhưng không phải như vậy trong
đồ thị có hướng
- Đồ thị liên thông v1 v2 v3
• Đồ thị không có hướng là liên
thông nếu tồn tại đường đi giữa v4 v5 v6
mọi cặp đỉnh trong đồ thị đó
• Đồ thị có hướng thỏa mãn điều v7
liên thông
kiện trên được gọi là liên thông v8 yếu
mạnh
• Nếu một đồ thị có hướng không v1 v2 v3
liên thông mạnh, nhưng đồ thị
không có hướng tương ứng liên
v4 v5 v6
thông, thì được gọi là liên thông
yếu
v7
liên thông
v8 mạnh
- Biểu diễn đồ thị
• Đánh số các đỉnh trong đồ thị từ 0 đến n-1
• Có thể dùng mảng hai chiều A có kích thước n x n (ma trận
vuông cỡ n) để lưu trữ đồ thị có hướng
− Với đồ thị không có trọng số, A[v][w] bằng true hoặc false
tùy theo cạnh (v, w) có mặt trong đồ thị hay không
− Với đồ thị có trọng số, A[v][w] bằng trọng số của cạnh (v, w)
nếu cạnh đó có mặt, hoặc bằng một giá trị đặc biệt (như
) nếu cạnh đó vắng mặt
• Với đồ thị không có hướng, cách biểu diễn trên (được gọi là
biểu diễn ma trận kề) lưu trữ mỗi cạnh hai lần
• Biểu diễn ma trận kề yêu cầu không gian O(n2)
- Ví dụ biểu diễn ma trận kề
0 1 2 3 4 5 6 7
v2 v3 0 F F F F F F T F
v1
1 F F F F T F F F
2 T F F F F F F F
v4 v5 v6
3 F F F F F T T F
v7 4 F F F F F F F F
v0 5 F F T F F F F F
6 F F F F F F F F
7 T F F F F F F F
- Biểu diễn danh sách kề
• Biểu diễn ma trận kề lãng phí không gian khi đồ thị thưa (có rất
ít cạnh)
− VD: Mỗi nút giao thông thường chỉ có 3-4 con đường giao
nhau số cạnh = O(n)
• Danh sách kề là cách tiếp cận hiệu quả để lưu trữ đồ thị thưa
− Đỉnh w kề với đỉnh v nếu (v, w) E
− Mỗi đỉnh giữ một danh sách các đỉnh kề với nó (các cạnh đi
ra). Nếu các cạnh có trọng số thì cũng lưu trữ các trọng số
vào danh sách kề này.
− Yêu cầu không gian O(|V|+|E|)
− Có thể dùng vector hoặc danh sách liên kết để lưu trữ danh
sách đỉnh kề
- Ví dụ biểu diễn danh sách kề
0 6, 7
v1 v2 v3 1 2
2 0
v4 v5 v6
3 5
4 1
v7 5 2
v0 6 3
7 4
- Duyệt đồ thị
- Duyệt đồ thị
• Là cách đi qua tất cả các đỉnh của đồ thị sao cho mỗi
đỉnh chỉ được thăm một lần
• Thăm bằng cách đánh số các đỉnh tăng dần
• Sau khi duyệt, trả về tập các cạnh đã đi qua
• Có hai cách duyệt:
1. Tìm kiếm theo chiều sâu
2. Tìm kiếm theo chiều rộng
- Tìm kiếm theo chiều sâu
(depth-first search)
• Với mỗi đỉnh v chưa được thăm:
− Thăm v
− Sau đó, thăm tiếp một đỉnh kề với v nhưng chưa được thăm
• Nếu v không có đỉnh kề hoặc tất cả các đỉnh kề với nó đã được
thăm, quay lui về đỉnh trước v
• Duyệt đồ thị kết thúc khi tiến trình thăm và quay lui nói trên
dẫn về đỉnh xuất phát s và tất cả các đỉnh kề với s khi đó đã
được thăm rồi
• Nếu vẫn còn đỉnh nào đó chưa được thăm, duyệt đồ thị bắt
đầu lại từ đỉnh đó
- Thuật toán tìm kiếm theo chiều sâu
depthFirstSearch()
1 với mỗi đỉnh v
2 num(v) = 0
3 edges =
4 i = 1
5 trong khi có một đỉnh v với num(v) bằng 0
6 DFS(v)
7 trả về edges
DFS(v)
1 num(v) = i++
2 với mỗi đỉnh w kề với v
3 nếu num(w) bằng 0
4 thêm cạnh (v, w) vào tập edges
5 DFS(w)
- Ví dụ tìm kiếm theo chiều sâu (1)
- Ví dụ tìm kiếm theo chiều sâu (2)
- Tìm kiếm theo chiều rộng
(breadth-first search)
• Tìm kiếm theo chiều rộng sẽ thăm tất cả các đỉnh kề
với đỉnh v trước khi tiếp tục với các đỉnh khác
• Trong khi đó, với tìm kiếm theo chiều sâu, ta thăm
một đỉnh kề của v, sau đó thăm tiếp một đỉnh kề của
đỉnh kề đó
- Thuật toán tìm kiếm theo chiều rộng
breadthFirstSearch()
1 với mỗi đỉnh v
2 num(v) = 0
3 edges =
4 i = 1;
5 trong khi có một đỉnh v với num(v) bằng 0
6 num(v) = i++
7 enqueue(v)
8 trong khi hàng đợi không rỗng
9 v = dequeue()
10 với mỗi đỉnh w kề với v
11 nếu num(w) bằng 0
12 num(w) = i++
13 enqueue(w)
14 thêm cạnh (v, w) vào tập edges
15 trả về edges
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
