Bài giảng Lý thuyết đồ thị - Chương 3: Các thuật toán duyệt đồ thị

Bài giảng Lý thuyết đồ thị - Chương 3: Các thuật toán duyệt đồ thị, cung cấp cho người đọc những kiến thức như: Ý tưởng chung của các thuật toán duyệt; Tìm kiếm theo chiều rộng; Ứng dụng trực tiếp cuả BFS; Tìm kiếm theo chiều sâu. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị - Chương 3: Các thuật toán duyệt đồ thị Chương 3 Các Thuật Toán Duyệt Đồ Thị (Graph Searching, Graph Traversal) 1 Các thuật toán duyệt đồ thị • Duyệt đồ thị: Graph Searching hoặc Graph Traversal • Duyệt qua mỗi đỉnh và mỗi cạnh của đồ thị • Ứng dụng: • Cần để khảo sát các tính chất của đồ thị • Là thành phần cơ bản của nhiều thuật toán trên đồ thị • Hai thuật toán duyệt cơ bản: • Tìm kiếm theo chiều rộng (Breadth First Search – BFS) • Tìm kiếm theo chiều sâu (Depth First Search – DFS) 2 Ý tưởng chung của các thuật toán duyệt Ý tưởng chung: • Trong quá trình thực hiện thuật toán, mỗi đỉnh ở một trong ba trạng thái: • Chưa thăm, thể hiện bởi màu trắng • Đã thăm (nhưng chưa duyệt xong), thể hiện bởi màu xám • Đã duyệt xong, thể hiện bởi màu đen • Trạng thái của đỉnh sẽ biến đổi theo qui tắc sau: • Thoạt đầu mỗi đỉnh đều có màu trắng (chưa thăm - not visited). • Đỉnh đã được thăm sẽ chuyển thành màu xám (trở thành đã thăm nhưng chưa duyệt xong - visited). • Khi tất cả các đỉnh kề của một đỉnh v là đã được thăm, đỉnh v sẽ có màu đen (đã duyệt xong – discovered). 3 Tìm kiếm theo chiều rộng Breadth-first Search (BFS) 4 Tìm kiếm theo chiều rộng Breadth-first Search • Input: Đồ thị G = (V, E), vô hướng hoặc có hướng. • Output: • d[v] = khoảng cách (độ dài của đường đi ngắn nhất) từ s (là đỉnh xuất phát tìm kiếm) đến v, với mọi v  V. d[v] =  nếu v không đạt tới được từ s. • [v] = u đỉnh đi trước v trong đường đi từ s (là đỉnh xuất phát tìm kiếm) đến v có độ dài d[v]. • Xây dựng cây BFS với gốc tại s chứa tất cả các đỉnh đạt tới được từ s. 5 Procedure BFS(s); (* Tìm kiếm theo chiều rộng bắt đầu từ đỉnh s *) begin color[s]  gray; d[s]  0; [s]  nil; Q  ; enqueue(Q,s); (* Nạp s vào Q *) Trắng: chưa thăm while Q   do xám: đã thăm begin đen: đã duyệt xong u  dequeue(Q); (* Lấy u từ Q *) for v Adj[u] do if color[v] = white then begin Q: hàng đợi các đỉnh được color[v]  gray; thăm d[v]  d[u] + 1; [v]  u; color[v]: màu của đỉnh v enqueue(Q,v) (* Nạp v vào Q *) d[v]: khoảng cách từ s đến v end; color[u]  black [u]: đỉnh đi trước v end; end; BEGIN (* Main Program*) Ví dụ: xem minh hoạ for v  V do (* Khởi tạo *) begin color[v]  white; d[v]  ; [v]  nil; end; for v  V do if color[v]=white then BFS(v); END. 6 Ví dụ (BFS) r s t u  0       v w x y Q: s 0 7 Ví dụ (BFS) r s t u 1 0    1   v w x y Q: w r 1 1 8 Ví dụ (BFS) r s t u 1 0 2   1 2  v w x y Q: r t x 1 2 2 9 Ví dụ (BFS) r s t u 1 0 2  2 1 2  v w x y Q: t x v 2 2 2 10 Ví dụ (BFS) r s t u 1 0 2 3 2 1 2  v w x y Q: x v u 2 2 3 11 Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Q: v u y 2 3 3 12 Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Q: u y 3 3 13 Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Q: y 3 14 Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Q:  15 Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Cây BFS(s) 16 Phân tích BFS • Việc khởi tạo đòi hỏi O(|V|). • Vòng lặp duyệt • Mỗi đỉnh được nạp vào và loại ra khỏi hàng đợi một lần, mỗi thao tác đòi hỏi thời gian O(1). Như vậy tổng thời gian làm việc với hàng đợi là O(V). • Danh sách kề của mỗi đỉnh được duyệt qua đúng một lần. Tổng độ dài của tất cả các danh sách kề là (|E|). • Tổng ...