CHƯƠNG 3
TÌM KIẾM TRÊN ĐỒ THỊ
Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ ‐ Tin học TP.HCM
Nội dung
Một số khái niệm
Thuật toán tìm kiếm theo chiều rộng
Thuật toán tìm kiếm theo chiều sâu
Ứng dụng
Một số khái niệm
2 đỉnh liên thông Đồ thị vô hướng liên thông Đồ thị có hướng Liên thông mạnh Miền liên thông Đỉnh khớp, cạnh cầu
Đường đi, chu trình Tính liên thông
Một số khái niệm
(cid:2869)
(cid:2870)
(cid:3038) trong đó:
(cid:2869)
(cid:3038)
(cid:3036)
(cid:3036)(cid:2878)(cid:2869)
Đường đi (Path): Đường đi từ đỉnh x đến đỉnh y trong đồ thị G=(V, E) là một dãy các đỉnh liên tiếp nối đỉnh x đến đỉnh y:
Độ dài đường đi: Là số cạnh của đường đi Đường đi đơn (simple): Là đường đi qua mỗi cạnh tối đa 1 lần.
Một số khái niệm
Chu trình (Cycle): Là đường đi có đỉnh đầu trùng với đỉnh cuối
Chu trình đơn: Mỗi cạnh xuất hiện tối đa 1 lần trong chu trình
Một số khái niệm
Hai đỉnh liên thông: Hai đỉnh x, y được gọi là liên thông với nhau nếu có đường đi từ x đến y.
thì
Đồ thị liên thông: Đồ thị vô hướng G=(V, E) được gọi là đồ thị liên thông nếu x liên thông với y.
Một số khái niệm
Đồ thị liên thông mạnh: Đồ thị có hướng G=(V, A) được gọi là đồ thị liên thông mạnh nếu thì x liên thông với y.
Thành phần liên thông: Là tập đỉnh liên thông với nhau và nếu bổ sung thêm 1 đỉnh khác thì không liên thông
Một số khái niệm
gọi
Cạnh cầu: Cho đồ thị G=(V, E). Cạnh là cầu nếu xóa cạnh e thì số thành phần liên thông tăng lên
gọi Đỉnh khớp: Cho đồ thị G=(V, E). Đỉnh là khớp nếu xóa các cạnh liên thuộc với v thì số thành phần liên thông tăng lên ít nhất là 2.
Tìm kiếm trên đồ thị
. Tìm kiếm trên đồ thị là phương pháp
Tìm kiếm trên đồ thị: Cho đồ thị G=(V, E) và 1 đỉnh xuất phát từ đỉnh s, và theo các cạnh liên thuộc để viếng thăm (duyệt) các đỉnh của đồ thị sao cho mỗi đỉnh được viếng thăm 1 lần, nhằm tìm nghiệm của bài toán
Kiểm tra xem có đường đi từ đỉnh u đến đỉnh v không? Kiểm tra đồ thị có liên thông hay không
Ví dụ:
Tìm kiếm trên đồ thị
Thuật toán tìm kiếm theo chiều rộng (Breadth First Search ‐ BFS)
Thuật toán tìm kiếm theo chiều sâu (Depth First Search ‐ DFS)
Trong chương này chúng ta sẽ tìm hiểu hai thuật toán tìm kiếm cơ bản trên đồ thị:
Tìm kiếm trên đồ thị theo chiều sâu
Thuật toán tìm kiếm theo chiều sâu (DFS):
Input: G(V, E) và đỉnh Output: Dãy đỉnh được viếng thăm
Bước 1: Viếng thăm đỉnh s Bước 2: Tìm đỉnh u: u kề với s và u chưa được viếng thăm • Nếu có đỉnh u thì đặt s=u và quay về Bước 1 • Nếu không có đỉnh u thì quay về đỉnh trước đỉnh s, và
tìm hướng đi khác.
• Thuật toán dừng khi không thể quay về đỉnh trước.
Tìm kiếm trên đồ thị theo chiều sâu
Đồ thị: Giả sử đồ thị lưu trong danh sách kề
Cài đặt: Cấu trúc dữ liệu
LinkedList[] v;
Dùng mảng bool[] visited để đánh dấu đỉnh đã viếng thăm hay chưa: • visited[i] = true: đỉnh i đã viếng thăm • visited[i] = false: đỉnh i chưa viếng thăm
bool[] visited;
Tìm kiếm trên đồ thị theo chiều sâu Cài đặt bằng Đệ quy
void DFS(int s) {
if (visited[s] == true) return; // Bước 1 visited[s] = true;
// process node s:…
// Bước 2 foreach (int u in v[s])
DFS(u);
}
Tìm kiếm trên đồ thị theo chiều sâu Cài đặt bằng Stack
// Dùng stack void DFS(int s) {
1. Đánh dấu s đã viếng thăm 2. Đưa s vào stack 3. while stack chưa rỗng {
{
Đánh dấu v đã viếng thăm Đẩy u vào lại stack Đẩy v vào stack
}
}
}
Tìm kiếm trên đồ thị theo chiều rộng
Thuật toán tìm kiếm theo chiều rộng (BFS):
Input: G(V, E) và đỉnh Output: Dãy đỉnh được viếng thăm
Bước 1: Gọi S1={s}, viếng thăm các đỉnh trong S1 Bước 2: Tìm các đỉnh (gọi là S2) kề với một trong những đỉnh S1, và chưa được viếng thăm, rồi viếng thăm các đỉnh trong S2 Bước 3: Tìm các đỉnh (gọi là S3) kề với một trong những đỉnh S2 và chưa được viếng thăm, rồi viếng thăm các đỉnh trong S3 … Cho đến khi không thể tìm thêm các đỉnh để viếng thăm
Tìm kiếm trên đồ thị theo chiều rộng
5
6
0
4
3
1
2
5
6
0
4
3
5
6
0
4
1
2
3
1
2
5
6
0
4
5
6
0
4
3
3
1
2
1
2
Ví dụ:
Tìm kiếm trên đồ thị theo chiều rộng
Những đỉnh gần với s nhất sẽ được viếng thăm trước
Các đỉnh chỉ được viếng thăm duy nhất 1 lần
Nhận xét
Tìm kiếm trên đồ thị theo chiều rộng
Đồ thị: Giả sử đồ thị lưu trong danh sách kề
Cài đặt: Cấu trúc dữ liệu
LinkedList[] v;
Dùng mảng bool[] visited để đánh dấu đỉnh đã viếng thăm hay chưa: • visited[i] = true: đỉnh i đã viếng thăm • visited[i] = false: đỉnh i chưa viếng thăm
bool[] visited;
Tìm kiếm trên đồ thị theo chiều rộng
Dùng queue để lưu trật tự các đỉnh được xử lý • Đỉnh mới sẽ được thêm vào cuối queue • Đỉnh ở đầu queue sẽ là đỉnh kế tiếp được xử lý
Cài đặt: Cấu trúc dữ liệu
Queue q;
Tìm kiếm trên đồ thị theo chiều rộng Cài đặt bằng hàng đợi
void BFS(int s) {
visited[s]=true; q.Enqueue(s); // Process node s
while(q.Count!=0) { s = q.Dequeue();
foreach (int u in v[s]) {
if (visited[u]) continue; visited[u]=true; q.Enqueue(u);
// Process node u
}
}
}
Tìm kiếm trên đồ thị
Mỗi phương thức DFS(s), BFS(s) cho phép thăm tất cả các đỉnh cùng thuộc một thành phần liên thông với s
Muốn duyệt hết tất cả các đỉnh của đồ thị phải gọi phương thức DFS() và BFS() nhiều lần, mỗi lần trên 1 đỉnh chưa được viếng thăm
Nhận xét
Ứng dụng
Tìm thuật toán cho các bài toán sau
Bài toán đường đi
• Hãy cho biết có đường đi từ đỉnh s đến đỉnh t hay không. Nếu có đường đi hãy chỉ ra 1 đường đi gồm thứ tự các đỉnh sẽ đi qua
• Tìm đường đi ngắn nhất (theo số cạnh đi qua) giữa 2
đỉnh trong đồ thị không có trọng số
Bài toán miền liên thông
• Kiểm tra tính liên thông của đồ thị vô hướng • Kiểm tra tính liên thông mạnh của đồ thị có hướng • Liệt kê các đỉnh trong từng thành phần liên thông • Xác định cạnh cầu và đỉnh khớp của đồ thị
Thuật toán tìm đường đi giữa 2 đỉnh
Bài toán: Giả sử s và t là 2 đỉnh của đồ thị. Hãy tìm đường đi từ s đến t
BFS(s) hay DFS(s) sẽ thăm tất cả các đỉnh thuộc cùng miền liên thông với s. Do đó sau khi BFS(s)/DFS(s) chạy xong mà đỉnh t chưa gán nhãn thì không có đường đi
Để ghi nhận đường đi ta dùng mảng pre[] với pre[i] = j ý nghĩa trên đường đi j là đỉnh trước của đỉnh i
Ý tưởng/Thuật toán:
Thuật toán tìm đường đi giữa 2 đỉnh
Đường đi tìm được bằng BFS(s) là đường đi qua ít đỉnh nhất
Cũng có thể áp dụng tìm đường đi có hướng bằng BFS/DFS
Nhận xét:
Thuật toán kiểm tra tính liên thông của đồ thị vô hướng
Bài toán: Cho đồ thị vô hướng. Kiểm tra đồ thị có liên thông không?
Duyệt đồ thị bằng DFS(0), BFS(0) với đỉnh 0
Nếu tồn tại 1 đỉnh chưa viếng thăm thì đồ thị không liên thông. Trong trường hợp mọi đỉnh đã viếng thăm thì đồ thị liên thông
Ý tưởng/Thuật toán:
Thuật toán kiểm tra tính liên thông của đồ thị có hướng
Bài toán: Cho đồ thị có hướng G=(V, E). Kiểm tra đồ thị có liên thông mạnh không?
Kiểm tra từ đỉnh 0 có đường đi đến mọi đỉnh x khác hay không bằng cách dùng BFS(0)/DFS(0)
T
T
Kiểm tra mọi đỉnh x có đường đi đến đỉnh 0 hay không • Tạo đồ thị chuyển vị
V E ( ,
)
với
G TE
u v {( , )|( , )
v u
E
}
Ý tưởng/Thuật toán
Thuật toán kiểm tra tính liên thông của đồ thị có hướng
Nhận xét rằng: Nếu trong G có đường đi từ u đến v thì trong (cid:3021) sẽ có đường đi từ v đến u và ngược lại.
Vậy để kiểm tra có đường đi từ mọi đỉnh x đến đỉnh 0 trong G hay không ta sẽ kiểm tra có đường đi từ đỉnh 0 đến các đỉnh x trong (cid:3021) hay không
Thuật toán tìm các thành phần liên thông
Bài toán: Cho đồ thị vô hướng. Tìm số thành phần liên thông của đồ thị
Gọi BFS(s)/DFS(s) thì các đỉnh thăm được từ s sẽ có cùng số hiệu thành phần liên thông
Tăng số hiệu thành phần liên thông và duyệt BFS/DFS cho đỉnh chưa được viếng thăm, …
Ý tưởng/Thuật toán:
Thuật toán kiểm tra cạnh cầu
Bước 1: Đếm số thành phần liên thông của đồ thị G Bước 2: Xóa cạnh e=(u, v) khỏi G gọi là G’ Bước 3: Đếm số thành phần liên thông của đồ thị mới G’. Nếu số thành phần liên thông của đồ thị mới G’ lớn hơn số thành phần liên thông của đồ thị cũ G thì e là cầu. Ngược lại e không là cầu
Thuật toán Kiểm tra cạnh cầu: Cho G=(V, E). Kiểm tra cạnh e=(u, v) có là cầu hay không
Thuật toán kiểm tra đỉnh khớp
Bước 1: Đếm số thành phần liên thông của đồ thị G Bước 2: Xóa mọi cạnh kề v khỏi G gọi là G’ Bước 3: Đếm số thành phần liên thông của đồ thị mới G’. Nếu số thành phần liên thông của đồ thị mới G’ lớn hơn số thành phần liên thông của đồ thị cũ G ít nhất là 2 thì v là đỉnh khớp. Ngược lại v không là đỉnh khớp
Thuật toán Kiểm tra đỉnh khớp: Cho G=(V, E). Kiểm tra đỉnh v có là đỉnh khớp hay không
