›
›

Bài giảng Lý thuyết đồ thị - Chương 3: Tìm kiếm trên đồ thị

pdf 26 trang phuongnguyen 7401
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 3: Tìm kiếm trên đồ thị", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_ly_thuyet_do_thi_chuong_3_tim_kiem_tren_do_thi.pdf

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 3: Tìm kiếm trên đồ thị

  1. Môn học: Lý thuyết đồ thị Chương 3: Tìm kiếm trên đồ thị Trường ĐHSPKT TP. HCM Khoa Công nghệ Thông tin Email: levinhcntt@yahoo.com
  2. Nội dung I. Duyệt đồ thị theo chiều sâu II. Duyệt đồ thị theo chiều rộng III. Tìm đường đi IV. Kiểm tra tính liên thông Chương 3 – Tìm kiếm trên đồ thị 2 Lý thuyết đồ thị
  3. I. Duyệt đồ thị theo chiều sâu ™Giới thiệu ƒ Duyệt đồ thị là quá trình đi qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được viếng thăm đúng một lần. ƒ Duyệt theo chiều sâu (Depth First Search – DFS) ƒ Duyệt theo chiều rộng (Breadth First Search – BFS) Chương 3 – Tìm kiếm trên đồ thị 3
  4. I. Duyệt đồ thị theo chiều sâu ™Nguyên lý ƒ Bắt đầu tìm kiếm từ một đỉnh v nào đócủa đồ thị. ƒ Sau đóchọn u là một đỉnh tùy ý kề với v (với đồ thị có hướng thì u là đỉnh sau, v là đỉnh đầu của cung uv) ƒ Lặp lại quá trình này với u cho đến khi không tìm được đỉnh kề tiếp theo nữa thì trở về đỉnh ngay trước đỉnh mà không thể đi tiếp để tìm qua nhánh khác. Chương 3 – Tìm kiếm trên đồ thị 4
  5. I. Duyệt đồ thị theo chiều sâu Thứ tự duyệt: d c b a g k l h f m e Chương 3 – Tìm kiếm trên đồ thị 5
  6. I.1. Cài đặt đệ quy B1: Lấy s là một đỉnh của đồ thị B2: Đặt v = s B3: Duyệt đỉnh v B4: Nếu ∀ đỉnh kề của v đều được duyệt, đặt v=đỉnh đã được duyệt trước đỉnh v, Nếu v = s thì đi đến Bước 6, ngược lại trở lại Bước 3. B5: Chọn u là đỉnh kề chưa được duyệt của v, đặt v = u, trở lại Bước 3 B6: Kết thúc Chương 3 – Tìm kiếm trên đồ thị 6
  7. I.1. Cài đặt đệ quy ™ Cài đặt bằng mã giả /* Khai báo các biến ChuaXet, Ke */ DFS(v) { Duyệt đỉnh (v); ChuaXet[v] = 0; /*Đánh dấu đã xét đỉnh v*/ for ( u ∈ Ke(v) ) if ( ChuaXet[u] ) DFS(u); }; void main() { /* Nhập đồ thị, tạo mảng Ke */ for (v ∈ V) ChuaXet[v] = 1; /* Khởi tạo cờ cho đỉnh */ for (v ∈ V) if ( ChuaXet[v] ) DFS(v); } Chương 3 – Tìm kiếm trên đồ thị 7
  8. I.2. Cài đặt không đệ quy ™ Thuật toán B1: Lấy s là một đỉnh của đồ thị B2: Đặt s vào STACK B3: Nếu STACK rỗng đi đến 7. B4: Lấy đỉnh p từ STACK B5: Duyệt đỉnh p B6: Đặt các đỉnh kề của p chưa được xét (chưa từng có mặt trong STACK) vào STACK, trở lại 3. B7: Kết thúc. Chương 3 – Tìm kiếm trên đồ thị 8
  9. I.Duyệt đồ thị theo chiều sâu ™Ý nghĩa ƒ Kiểm tra đường đi giữa 2 đỉnh ƒ Chia đồ thị thành các thành phần liên thông ƒ Xây dựng cây khung của đồ thị ƒ Kiểm tra xem đồ thị có chu trình hay không Chương 3 – Tìm kiếm trên đồ thị 9
  10. Nội dung I. Duyệt đồ thị theo chiều sâu II. Duyệt đồ thị theo chiều rộng III. Tìm đường đi IV. Kiểm tra tính liên thông Chương 3 – Tìm kiếm trên đồ thị 10 Lý thuyết đồ thị
  11. II. Duyệt đồ thị theo chiều rộng ™Nguyên lý ƒ Bắt đầu từ một đỉnh v bất kỳ. ƒ Duyệt tất cả những đỉnh kề của v lưu vào một tập T(u) (với đồ thị có hướng thì T(u) là tập các đỉnh u với u là đỉnh sau, v là đỉnh đầu của cung uv). ƒ Sau đótiếp tục xét các đỉnh u thuộc T(u) và áp dụng lại cách duyệt giống như với v. Chương 3 – Tìm kiếm trên đồ thị 11
  12. II. Duyệt đồ thị theo chiều rộng Thứ tự duyệt: d e c b f a g m h k l Chương 3 – Tìm kiếm trên đồ thị 12
  13. II.1. Cài đặt bằng hàng đợi B1: Lấy s là một đỉnh của đồ thị B2: Đặt s vào QUEUE B3: Lặp nếu QUEUE chưa rỗng. a.Lấy đỉnh p từ QUEUE b.Duyệt đỉnh p c.Đặt các đỉnh kề của p chưa được xét (chưa từng có mặt trong QUEUE) vào QUEUE. d.Kết thúc lặp Chương 3 – Tìm kiếm trên đồ thị 13
  14. II.1. Cài đặt bằng hàng đợi /* Khai báo các biến ChuaXet, Ke */ BFS(v) { QUEUE = ∅; QUEUE ⇐ v; ChuaXet[v] = 0;/*Đánh dấu đã xét đỉnh v*/ while ( QUEUE ≠ ∅ ) { p ⇐ QUEUE; Duyệt đỉnh p; for ( u ∈ Ke(p) ) if ( ChuaXet[u] ) { QUEUE ⇐ u; ChuaXet[u] = 0;/*Đánh dấu đã xét đỉnh */ } } } void main() /* Nhập đồ thị, tạo biến Ke */ { for ( v ∈ V ) ChuaXet[v] = 1; /* Khởi tạo cờ cho đỉnh */ for ( v ∈ V) if ( ChuaXet[v] ) BFS(v); } Chương 3 – Tìm kiếm trên đồ thị 14
  15. II.2. Cài đặt bằng thuật toán loang Chương 3 – Tìm kiếm trên đồ thị 15
  16. II.2. Cài đặt bằng thuật toán loang ™ Bước 1: Khởi tạo ƒ Bắt đầu từ đỉnh s. Đánh dấu đỉnh s, các đỉnh khác s đầu chưa bị đánh dấu ƒ X = {s}, Y = Ø ™ Bước 2: Lặp lại cho đến khi X= Ø ƒ Gán Y= Ø. ƒ Với mọi đỉnh u ∈ X • Xét tất cả các đỉnh v kề với u mà chưa bị đánh dấu. Với mỗi đỉnh đó: – Đánh dấu v –Lưu đường đi, đỉnh liền trước v trong đường đi từ s Æ v là u. – Đưa v vào tập Y ƒ Gán X = Y Chương 3 – Tìm kiếm trên đồ thị 16
  17. II. Duyệt đồ thị theo chiều rộng ™Ý nghĩa ƒ Kiểm tra đường đi giữa 2 đỉnh ƒ Chia đồ thị thành các thành phần liên thông ƒ Xây dựng cây khung của đồ thị ƒ Tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại Chương 3 – Tìm kiếm trên đồ thị 17
  18. Nội dung I. Duyệt đồ thị theo chiều sâu II. Duyệt đồ thị theo chiều rộng III. Tìm đường đi IV. Kiểm tra tính liên thông Chương 3 – Tìm kiếm trên đồ thị 18 Lý thuyết đồ thị
  19. III. Tìm đường đi ™Bài toán ƒ Cho đồ thị G, s và t là hai đỉnh tùy ý của đồ thị. Hãy tìm đường đi từ s đến t. ™Phương pháp ƒ Bắt đầu từ đỉnh s, Sử dụng DFS hoặc BFS để duyệt đồ thị. • Tìm thấy ChuaXet(t) = 0 • Không tìm thấy ChuaXet(t) = 1 ƒ Sử dụng thêm mảng Truoc[] để lưu vết Chương 3 – Tìm kiếm trên đồ thị 19
  20. III.1. Tìm đường đi theo chiều sâu /* Khai báo các biến ChuaXet, Ke */ DFS(v); { Duyệt đỉnh (v); ChuaXet[v] = 0; for ( u ∈ Ke(v) ) if ( ChuaXet[u] ) { Truoc[u] = v; /* Lưu vết*/ DFS(u); } } main() // Nhập đồ thị, tạo biến Ke { for ( v ∈ V ) ChuaXet[v] = 1; // Khởi tạo cờ cho đỉnh DFS(s); } Chương 3 – Tìm kiếm trên đồ thị 20
  21. III.2. Tìm đường đi theo chiều rộng /* Khai báo các biến ChuaXet, Ke , QUEUE */ BFS(v); { QUEUE = ∅; QUEUE ⇐ v; ChuaXet[v] = 0; while ( QUEUE ≠ ∅ ) { p ⇐ QUEUE; Duyệt đỉnh p; for ( u ∈ Ke(p) ) if ( ChuaXet[u] ) { QUEUE ⇐ u; ChuaXet[u] = 0; Truoc[u] = p;/*Lưu vết*/ } } } main() // Nhập đồ thị, tạo biến Ke { for ( v ∈ V ) ChuaXet[v] = 1; // Khởi tạo cờ cho đỉnh BFS(s); } Chương 3 – Tìm kiếm trên đồ thị 21
  22. III.2. Tìm đường đi theo chiều rộng Khôi phục đường đi từ s đến t s Æ x1 Æ x2 Æ Æ xn Æ t Cài đặt: v = t; while (v != s) { printf (v); v = Truoc[v]; } Chương 3 – Tìm kiếm trên đồ thị 22
  23. Nội dung I. Duyệt đồ thị theo chiều sâu II. Duyệt đồ thị theo chiều rộng III. Tìm đường đi IV. Kiểm tra tính liên thông Chương 3 – Tìm kiếm trên đồ thị 23 Lý thuyết đồ thị
  24. IV. Kiểm tra tính liên thông ™Bài toán ƒ Tính số thành phần liên thông của đồ thị, và xác định những đỉnh thuộc cùng một thành phần liên thông. ™Phương pháp ƒ Sử dụng DFS và BFS ƒ Biến inconnect đếm số thành phần liên thông của đồ thị. ƒ Mảng index[] lưu chỉ số của các thành phần liên thông. Chương 3 – Tìm kiếm trên đồ thị 24
  25. IV.1. Tìm theo chiều rộng /* Khai báo các biến ChuaXet, Ke, index*/ DFS(v); { Duyệt đỉnh (v); index[v] = inconnect; ChuaXet[v] = 0; for ( u ∈ Ke(v) ) if ( ChuaXet[u] ) DFS(u); } main() { /* Nhập đồ thị, tạo biến Ke */ for ( v ∈ V ) ChuaXet[v] = 1; /* Khởi tạo cờ cho đỉnh */ inconnect = 0; for ( v ∈ V ) if ( ChuaXet[v] ) { inconnect ++; DFS(v); } } Chương 3 – Tìm kiếm trên đồ thị 25
  26. IV.2. Tìm theo chiều sâu /* Khai báo các biến toàn cục ChuaXet, Ke, QUEUE, index */ BFS(v) { QUEUE = 0; QUEUE ⇐ v; ChuaXet[v] = 0; while ( QUEUE ≠ 0 ) { p ⇐ QUEUE; Duyệt đỉnh p; index[p] = inconnect; for ( u ∈ Ke(p) ) if ( ChuaXet[u] ) { QUEUE ⇐ u;ChuaXet[u] = 0; } } } main() { for ( v ∈ V ) ChuaXet[v] = 1; inconnect = 0; for ( v ∈ V ) if ( ChuaXet[v] ) { inconnect + + ; BFS(v); } } Chương 3 – Tìm kiếm trên đồ thị 26