›
›

Bài giảng Toán ứng dụng - Bài 4: Biểu diễn đồ thị và các thuật toán tìm kiếm

pdf 48 trang hapham 1650
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán ứng dụng - Bài 4: Biểu diễn đồ thị và các thuật toán tìm kiếm", để 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_toan_ung_dung_bai_4_bieu_dien_do_thi_va_cac_thuat.pdf

Nội dung text: Bài giảng Toán ứng dụng - Bài 4: Biểu diễn đồ thị và các thuật toán tìm kiếm

  1. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: MÔN HỌC: TOÁN ỨNG DỤNG Bài 1: CƠ SỞ LOGIC Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI Bài 3: LÝ THUYẾT ĐỒ THỊ Bài 4: BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM Bài 5: CÂY VÀ CÁC ỨNG DỤNG BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  2. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Bài 4: BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM 1. BIỂU DIỄN ĐỒ THỊ 1.1 Danh sách liền kề 1.2 Ma trận kề 1.3 Ma trận trọng số 1.4 Ma trận liên thuộc 2. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 2.1 Giới thiệu bài toán 2.2 Thuật toán Dijkstra 2.3 Thuật toán Floyd 3. CÁC THUẬT TOÁN TÌM KIẾM 3.1 Giới thiệu 3.2 Duyệt đồ thị theo chiều sâu 3.3 Duyệt đồ thị theo chiều rộng BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  3. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.1 Danh sách liền kề - Danh sách liền kề là một cách biểu diễn đồ thị không có cạnh bội bằng cách liệt kê tất cả các đỉnh nối với mỗi đỉnh của đồ thị BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  4. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.1 Danh sách liền kề Ví dụ: Danh sách liền kề của đồ thị vô hướng G Đỉnh Đỉnh liền kề 1 3,2 2 1,3,5 3 1,2,4 4 3,5,6 5 2,4,6 6 4,5 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  5. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.1 Danh sách liền kề Ví dụ: Danh sách liền kề của đồ thị có hướng G1 Đỉnh đầu Đỉnh cuối 1 2,3 2 3 2 4 3 5 4,6 6 5 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  6. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận liền kề Xét đơn đồ thị vô hướng G=(V,E), với tập đỉnh V={v1, v2, ,vn } và tập cạnh E={e1, e2, , em }. Ma trận liền kề AG của đồ thị G là ma trận 0-1 vuông cấp nxn. AG= (aij), trong đó: 1, nếu (vi,vj) là một cạnh của G aij = 0,nếu không có cạnh nối đỉnh vi với vj BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  7. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận liền kề Ví dụ: Ma trận liền kề của đơn đồ thị vô hướng G 3 5 1 2 3 4 5 6 1 0 1 1 0 1 0 2 1 0 1 1 0 0 1 6 3 1 1 0 0 1 0 4 0 1 0 0 1 1 5 1 0 1 1 0 1 2 4 6 0 0 0 1 1 0 1- Ma trận liền kề của đơn đồ thị vô hướng G có dòng, cột đối xứng qua đường chéo 2- Tổng giá trị trên một dòng (hoặc cột) bằng số bậc của đỉnh i. BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  8. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận liền kề Ví dụ: Ma trận liền kề của đa đồ thị vô hướng G 3 5 1 2 3 4 5 6 1 0 1 1 0 0 0 2 1 0 2 2 0 0 1 6 3 1 2 0 0 1 0 4 0 2 0 0 1 1 5 0 0 1 1 0 3 2 4 6 0 0 0 1 3 0 aij = k - tổng số cạnh nối hai đỉnh BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  9. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận liền kề Ví dụ: Ma trận liền kề của đơn đồ thị có hướng G* 1 2 3 4 5 1 2 1 0 1 1 0 0 2 0 0 0 1 1 3 0 0 0 1 0 4 0 0 0 0 0 5 1 0 0 0 0 3 4 5 Ma trận liền kề của đơn đồ thị có hướng G không có dòng, cột đối xứng BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  10. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận trọng số - Trong thực tế chúng ta thường giải quyết những tình huống như sau: từ địa điểm A đến địa điểm B trong thành phố, chúng ta chọn đường đi ngắn nhất (xét đến độ dài), có lúc lại cần chọn đường đi nhanh nhất (xét đến thời gian) và có lúc phải cân nhắc để chọn đường đi có chi phí thấp nhất, v.v - Khi chúng ta gán một giá trị số thực dương cho mỗi cạnh của đồ thị G thì chúng ta có đồ thị có trọng số. - Chúng ta có thể xem đồ thị G bất kỳ là đồ thị có trọng số mà tất cả các cạnh có trọng số bằng 1. BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  11. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận trọng số BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  12. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận trọng số - Đồ thị G = (V,E) gọi là đồ thị có trọng số nếu mỗi cạnh (hay cung) e được gán với một số thực w(e), gọi là trọng số của e (hay chiều dài, trọng lượng của cạnh e). v2 6 v4 3 5 v1 6 8 v6 7 9 v3 3 v5 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  13. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận trọng số - Mỗi đường đi m(u,v) từ đỉnh u đến đỉnh v, có trọng số bằng tổng trọng số các cạnh mà nó đi qua. - Khoảng cách d(u,v) giữa hai đỉnh u và v là đường đi có trọng số nhỏ nhất trong các đường đi từ u đến v. d(u,v)=min(m(u,v)) BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  14. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận trọng số Ma trận trọng số D= d(ij) , xác định như sau: 0, khi đỉnh trùng dij = w(i,j), trọng số của cạnh nối giữa hai đỉnh , nếu không có cạnh nối giữa hai đỉnh BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  15. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.3 Ma trận trọng số Ví dụ: Vẽ ma trận trọng số biểu diễn đồ thị vô hướng G v1 v2 v3 v4 v5 v6 v2 6 v4 3 5 v1 0 3 7 v1 v2 3 0 6 6 6 8 v6 v3 7 6 0 3 7 9 v4 6 0 8 5 v3 3 v5 v5 3 8 0 9 v6 5 9 0 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  16. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận trọng số Ví dụ: Lập ma trận trọng số biểu diễn đồ thị có hướng G BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  17. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.2 Ma trận trọng số Ví dụ: 0 5 31 40 0 27 73 26 0 8 49 25 38 D 0 16 70 0 9 23 0 12 10 0 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  18. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.3 Ma trận liên thuộc Ma trận liên thuộc biểu diễn quan hệ giữa cạnh liên thuộc và đỉnh kề. Ma trận M= (mij), xác định như sau: 1 nếu cạnh e nối với đỉnh v mij = j i 0 nếu cạnh ej không nối với đỉnh vi BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  19. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Biểu diễn đồ thị 1.3 Ma trận liên thuộc Ví dụ: Xây dựng ma trận liên thuộc cho đồ thị G dưới đây e1 e2 e3 e4 e5 e6 v1 v2 v3 v4 v5 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  20. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.1 Giới thiệu bài toán Cho đơn đồ thị liên thông, có trọng số dương G=(V,E). Bài toán 1: Tìm đường đi ngắn nhất từ một đỉnh u đến mỗi đỉnh v của đồ thị G. Bài toán 2: Tìm đường đi ngắn nhất giữa mỗi cặp đỉnh của đồ thị G. 5 B D 6 1 A Z 1 8 2 2 3 C E 10 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  21. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Thuật toán tìm đường đi ngắn nhất từ đỉnh u đến mỗi đỉnh v của đồ thị G, được nhà toán học người Hà Lan E. Dijkstra đề xuất vào năm 1959. Thuật toán thực hiện theo cách gán nhãn tại mỗi đỉnh. Thuật ngữ: w(x,y) : trọng số dương của cạnh (x,y); w(x,y) là ∞ (vô cùng lớn) nếu hai đỉnh không kề nhau. d(v) : độ dài đường đi từ đỉnh xuất phát tới đỉnh v. p(v) : đỉnh đứng ngay trước đỉnh v trên đường đi từ đỉnh xuất phát đến đỉnh v. Nhãn của đỉnh v : gồm cặp (d(v), p(v)) T : Tập các nút mà đường đi ngắn nhất đã được xác định. BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  22. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Gán T = ø; p(v) = NULL với mọi đỉnh v d(a)=0; /* a là đỉnh xuất phát Với mỗi đỉnh v còn lại thì d(v) = ∞; Repeat u =(u T | d(u) là bé nhất); T = T ∪ {u}; for ((v là đỉnh kề của u) và v T) if d(v) > d(u) + w(u,v) then d(v) = d(u) + w(u,v) p(v) = u Until (T=V) BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  23. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 1: Tìm đường đi ngắn nhất từ A đến mỗi đỉnh khác của đồ thị G dưới đây B 5 D 6 1 Z A 1 8 2 2 3 C E 10 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  24. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 1: d(D) =∞ = d(A)+w(A,D)=0+∞=∞ d(B) =∞ > d(A)+w(A,B)=0+1=1 d(E) =∞ = d(A)+w(A,E)=0+∞=∞ d(C) =∞ > d(A)+w(A,C)=0+2=2 d(Z) =∞ = d(A)+w(A,Z)=0+∞=∞ (∞,-) (∞,-) (∞,-) (1,a) (∞,-) B D B D 5 6 5 6 1 (∞,-) 1 (∞,-) 8 Z 8 Z A 1 A 1 (0,-) 2 2 2 3 (0,-)* 2 3 C E C E 10 10 (∞,-) (∞,-) (∞,-) (2,a) (∞,-) BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  25. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 1: (∞,-) (1,a)* (6,b) (1,a)* (6,b) B D 5 6 B D 6 1 (∞,-) 1 5 (∞,-) 8 Z 8 Z A 1 2 A 1 2 (0,-)* 2 3 (0,-)* 2 3 C E C E 10 (∞,-) 10 (2,a) (2,a)* (12,c) (∞,-) d(C) =2 = d(B)+w(B,C)=1+1=2 d(D) =∞ > d(B)+w(B,D)=1+5=6 d(D) =6 > d(C)+w(C,D)=2+8=10 d(E) =∞ = d(B)+w(B,E)=0+∞=∞ d(E) =∞ > d(C)+w(C,E)=2+10=12 d(Z) =∞ = d(B)+w(B,Z)=0+∞=∞ d(Z) =∞ = d(C)+w(C,Z)=0+∞=∞ BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  26. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 1: (1,a)* (6,b)* (1,a)* (6,b)* (12,d) B D 5 6 B D 1 (12,d) 1 5 (11,e) 8 Z 8 6 Z A 1 2 A 1 2 (0,-)* 2 3 (0,-)* 2 3 C E C E 10 (8,d) (12,c) 10 (2,a)* (2,a)* (8,d)* d(E) =12 > d(D)+w(D,E)=6+2=8 d(Z) =∞ = d(D)+w(D,Z)=6+6=12 d(Z) =12 >d(E)+w(E,Z)=8+3=11 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  27. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 1: (1,a)* (6,b)* B D 1 5 (11,e)* 6 8 Z A 1 2 (0,-)* 2 3 C E 10 (2,a)* (8,d)* BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  28. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 1: Lập bảng để giải bài toán tìm đường đi ngắn nhất Bước Tập T a b d c e z 0 ø (0,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 1 a (0,-)* (1,a) ( ,-) (2,a) ( ,-) ( ,-) 2 ba - (1,a)* (6,b) (2,a) ( ,-) ( ,-) 3 cba - - (6,b) (2,a) * (12,c) ( ,-) 4 dcba - - (6,b)* - (8,d) (12,d) 5 edcba - - - - (8,d)* (11,e) 6 zedcba - - - - - (11,e)* BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  29. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 1: Nhận xét bảng kết quả đã thu được. 1/. Độ dài đường đi ngắn nhất từ A đến các đỉnh là ->B: 1 ->C: 2 ->D: 6 ->E: 8 ->Z: 11 2/. Để vẽ đường đi ngắn nhất từ A đến đỉnh Z, chúng ta sử dụng cách đi ngược từ Z về A. Cụ thể là Z <- E <- D <- B <- A. 3/. Đường đi ngắn nhất từ A đến Z không đi qua C. Vậy đường đi ngắn nhất không đi qua tất cả các đỉnh của đồ thị. BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  30. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 2: Tìm đường đi ngắn nhất giữa A và W trong đồ thị G dưới đây 5 3 v w 2 5 a 2 1 z 3 1 2 x y 1 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  31. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 2: Do bài toán chỉ cần tìm đường đi ngắn nhất từ A đến W trong đồ thị G nên chúng ta đổi điều kiện kết thúc thuật toán Dijkstra như sau: Repeat u =(u T | d(u) là bé nhất); T = T ∪ {u}; for ((v là đỉnh kề của u) và v T) if d(v) > d(u) + w(u,v) then d(v) = d(u) + w(u,v) p(v) = u Until ( đỉnh đích chứa trong tập T) BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  32. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 2: Tìm đường đi ngắn nhất giữa A và W trong đồ thị G Bước Tập T a v x y w z 0 ø (0.-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 1 a (0,-)* (2,a) (1,a) ( ,-) (5,a) ( ,-) 2 xa - (2,a) (1,a)* (2,x) (4,x) ( ,-) 3 yxa - (2,a) - (2,x)* (3,y) (4,y) 4 vyxa - (2,a)* - - (3,y) (4,y) 5 wvyxa - - - - (3,y)* (4,y) 6 Kết thúc vì đỉnh đến w chứa trong tập T BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  33. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra H Ví dụ 3: 4 G 1 4 Cho đồ thị có trọng số G. 5 K 3 9 Z Tìm đường đi B 9 9 10 ngắn nhất từ 2 E A đến mỗi đỉnh 6 8 4 2 F của đồ thị. 12 D 9 3 A 9 8 9 C BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  34. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 4: Cho đồ thị có trọng số G = (V, E), tìm đường đi ngắn nhất giữa A và H. 4 B E 4 3 4 2 A b C H K 2 3 3 2 4 4 5 D 6 G BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  35. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.2 Thuật toán Dijkstra Ví dụ 5: Tìm đường đi v1 v2 v3 v4 v5 v6 v7 ngắn nhất từ v1 v1 đến các đỉnh 0 5 30 40 khác của v2 0 27 73 đồ thị v3 có trọng số 26 0 8 40 25 38 được biểu diễn v4 0 16 20 trong v5 ma trận M 70 0 20 12 hình bên. v6 22 22 12 v7 50 10 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  36. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.3 Thuật toán Floyd Giới thiệu Để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị G=(V,E), chúng ta sử dụng thuật toán Floyd được công bố năm 1962. Việc tìm đường đi ngắn nhất dựa trên nguyên tắc sau: " Nếu k là đỉnh nằm trên đường đi ngắn nhất từ i đến j thì đoạn đường từ i đến k và từ k đến j cũng ngắn nhất" Ak[i,j]=min(Ak-1[i,j], Ak-1[i,k]+Ak-1[k,j]) BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  37. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.3 Thuật toán Floyd BEGIN for i := 1 to n do for j := 1 to n do begin D[i,j] := C[i,j] ; P[i,j] := 0 end ; for k := 1 to n do for i := 1 to n do for j := 1 to n do if D[i,k] + D[k,j] < D[i,j] then begin D[i,j] := D[i,k] + D[k,j] ; P[i,j] := k end END. BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  38. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 2.3 Thuật toán Floyd Ví dụ: 1 2 3 1 0 4 5 W = D0 = 2 2 0 1 5 3 3 0 4 2 3 1 2 3 3 1 0 0 0 2 P = 2 0 0 0 3 0 0 0
  39. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 1 2 3 1 1 5 D0 = 0 4 5 2 2 0 4 2 3 k = 1 3 3 0 2 3 1 2 3 1 0 4 5 D1[2,3] = min( D0[2,3], D0[2,1]+D0[1,3] ) 1 D = = min (, 7) 2 2 0 7 = 7 3 3 0 P[2,3]=1 1 2 3 1 0 0 0 D1[3,2] = min( D0[3,2], D0[3,1]+D0[1,2] ) P = 2 0 0 1 = min (3,) 3 0 0 0 = 3
  40. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 1 2 3 1 1 5 D =1 0 4 5 4 2 3 2 2 0 7 k = 2 3 2 3 3 0 1 2 3 1 0 4 5 D2[1,3] = min( D1[1,3], D1[1,2]+D1[2,3] ) D2 = 2 2 0 7 = min (5, 4+7) = 5 3 5 3 0 1 2 3 2 1 1 1 1 0 0 0 D [3,1] = min( D [3,1], D [3,2]+D [2,1] ) = min (, 3+2) P = 2 0 0 1 = 5 3 2 0 0 P[3,1] = 2
  41. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Bài toán đường đi ngắn nhất 1 2 3 1 5 D2 = 1 0 4 5 4 3 k = 3 2 2 2 0 7 2 3 3 5 3 0 1 2 3 1 0 4 5 3 D = D3[1,2] = min(D2[1,2], D2[1,3]+D2[3,2] ) 2 2 0 7 = min (4, 5+3)) 3 5 3 0 = 4 1 2 3 1 0 0 0 D3[2,1] = min(D2[2,1], D2[2,3]+D2[3,1] ) P = 2 0 0 1 = min (2, 7+ 5) 3 2 0 0 = 2 BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM
  42. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Duyệt đồ thị 3.1 Giới thiệu Với một đồ thị có nhiều nút, việc kiểm tra tính liên thông của đồ thị là bài toán lớn, cần có cách thức để thực hiện nhanh, chính xác. Hai cách duyệt đồ thị phổ biến được áp dụng: 1. Duyệt đồ thị theo chiều sâu (Depth First Search - DFS) 2. Duyệt đồ thị theo chiều rộng (Breadth First Search - BFS) DFS BFS
  43. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Duyệt đồ thị 3.2 Duyệt đồ thị theo chiều sâu Xuất từ một đỉnh v bất kỳ của đồ thị G, chúng ta thực hiện như sau: Bước 1: đánh dấu v đã được duyệt. Bước 2: thực hiện đánh dấu đã duyệt với mỗi đỉnh w chưa duyệt kề với v, Bước 3: làm lại bước 2 cho đến khi tất cả các đỉnh được duyệt. DFS
  44. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Duyệt đồ thị 3.2 Duyệt đồ thị theo chiều sâu Ví dụ: Thực hiện duyệt đồ thị theo chiều sâu trên đồ thị G dưới đây: v1 v2 v3 v4 v5 v6 v7 v8 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Bảng duyệt v1 v2 v6 v3 v4 v8 v7 v5
  45. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Duyệt đồ thị 3.3 Duyệt đồ thị theo chiều rộng Xuất từ một đỉnh v bất kỳ của đồ thị G, chúng ta thực hiện như sau: Bước 1: đánh dấu đã duyệt cho một đỉnh v bất kỳ. Bước 2: chọn đỉnh v đã được duyệt nhưng có đỉnh kề chưa được duyệt. Việc chọn đỉnh v được xét ưu tiên cho các đỉnh được đánh dấu duyệt sớm. Bước 3: thực hiện đánh dấu đã duyệt với tất cả các đỉnh w kề với v, Bước 4: làm lại bước 2 cho đến khi tất cả các đỉnh được duyệt. BFS
  46. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Duyệt đồ thị 3.3 Duyệt đồ thị theo chiều rộng
  47. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Duyệt đồ thị 3.3 Duyệt đồ thị theo chiều rộng Ví dụ: Thực hiện duyệt đồ thị theo chiều rộng trên đồ thị G dưới đây: v1 v2 v3 v4 v5 v6 v7 v8 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Bảng duyệt v1 v2 v5 v6 v3 v7 v4 v8
  48. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Duyệt đồ thị 3.3 Duyệt đồ thị theo chiều rộng Ví dụ: Thực hiện duyệt đồ thị theo chiều rộng trên đồ thị G dưới đây: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9