›
›

Thuật giải - Heapsort

pdf 142 trang vanle 3180
Download
Bạn đang xem 20 trang mẫu của tài liệu "Thuật giải - Heapsort", để 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:

  • pdfthuat_giai_heapsort.pdf

Nội dung text: Thuật giải - Heapsort

  1. HEAPSORT • Giải thuật sắp xếp (sorting algorithm) • Heaps • Thuật giải Heapsort • Hàng đợi ưu tiên (priority queue) 1
  2. GIẢI THUẬT SẮP XẾP • Input: một dãy n số (a1, a2, , an) • Output: một hoán vị của input (a’1, a’2, , a’n) sao cho a’1 a’2 a ’n 2
  3. HEAPS • Đólàmột mảng các đối tượng được biểu diễn bởi một cây nhị phân có thứ tự và cân bằng • Mỗi nút tương ứng với một phần tử của mảng, gốc ứng với phần tử đầu tiên của mảng 3
  4. HEAPS • Cây được lấp đầy trên tất cả các mức, ngoại trừ mức thấp nhất được lấp đầy từ bên trái sang (có thể chưa lấp đầy) • Một heap biểu diễn một mảng A có hai đặc tính: . length[A], là số phần tử của mảng . heap-size[A], là số phần tử của A được biểu diễn bởi heap 4
  5. HEAPS 5
  6. HEAPS • Chỉ số của cha, con trái và con phải của nút i có thể tính: . PARENT( i) return i/2 . LEFT(i) return 2i . RIGHT(i) return 2i+ 1 6
  7. HEAPS • Có hai loại heap nhị phân, max-heap và min-heap . Trong max-heap A[PARENT(i)] A[i] với mọi nút i khác gốc phần tử lớn nhất được lưu trữ tại g ốc . Trong min-heap A[PARENT(i)] A[i] với mọi nút i khác gốc phần tử nhỏ nhất được lưu trữ tại gốc 7
  8. HEAPS • Các thủ tục trên max-heap dùng cho sắp xếp . MAX-HEAPIFY tạo một max-heap có gốc tại nút i . BUILD-MAX-HEAP xây dựng một max-heap từ một mảng không thứ tự . HEAPSORT sắp xếp một mảng 8
  9. MAX-HEAPIFY • Đầu vào là một mảng (heap) A và chỉ số i trong mảng • Các cây nhị phân được định gốc tại LEFT(i) và RIGHT(i) là các max-heap nhưng A[i] có thể nhỏ hơn các con c ủa nó • MAX-HEAPIFY đẩy giá trị A[i] xuống sao cho cây con định gốc tại A[i] là một max-heap 9
  10. MAX-HEAPIFY 10
  11. MAX-HEAPIFY • Thời gian chạy của MAX-HEAPIFY từ dòng 1 đến 8 là O(1) • Mỗi cây con có kích thước lớn nhất là 2n/3 nếu heap có n nút vì vậy thời gian ch ạy của MAX-HEAPIFY là T(n) T(2n/3)+ O(1) • Giải hệ thức này ta có T(n) = O(lg n)=O(h) (h là chiều cao cây) 11
  12. BUILD-MAX-HEAP • Các nút có chỉ số n/2 +1, n/2 +2, , n trong A[1 n] là các lá của cây, mỗi nút như vậy là mộ t max-heap • BUILD-MAX-HEAP áp dụng MAX-HEAPIFY cho các nút con khác lá của cây từ dưới lên gốc bắt đầu từ nút n/2 • Kết quả là một max-heap tương ứng với A[1 n] 12
  13. BUILD-MAX-HEAP 13
  14. BUILD-MAX-HEAP 14
  15. BUILD-MAX-HEAP • Bất biến vòng lặp: Tại điểm bắt đầu của mỗi lần lặp của vòng lặp 2-3, mỗi nút i+1, i+2, , n là gốc của một max-heap • Bất biến này đúng trước lần lặp đầu tiên, sau đóduy trìcho mỗi lần lặp tiếp theo 15
  16. BUILD-MAX-HEAP • Khởi đầu: i = n/2 , mỗi nút n/2 +1, n/2 +2, , n là một lá, chúng là gốc của một max-heap • Duy trì: MAX-HEAPIFY(A, i) đảm bảo nút i và các con của nó là các gốc của các max-heap, bất biến vòng lặp thỏa khi i giảm và trở về đầu vòng lặp • Kết thúc: Khi i = 0, mỗi nút 1, 2, , n là gốc của một max- heap 16
  17. BUILD-MAX-HEAP • Thời gian chạy của BUILD-MAX-HEAP là O(nlgn), vì có n lần gọi MAX-HEAPIFY, mỗi lần chi phí lgn • Thực sự thời gian chạy của BUILD-MAX-HEAP là O(n) 17
  18. HEAPSORT • Heapsort sử dụng BUILD-MAX-HEAP để xây dựng một max- heap trên mả ng input A[1 n] • Hoán đổi giá trị A[1] với A[n] • Loại nút n ra khỏi heap và chuyển A[1 (n-1)] thành một max- heap • Lặp lại các bước trên cho đến khi heap chỉ còn một phần tử 18
  19. HEAPSORT 19
  20. HEAPSORT 20
  21. HEAPSORT • Chi phí của BUILD-MAX-HEAP là O(n) • Có n-1 lời gọi MAX-HEAPIFY, mỗi lời gọi chi phí O(lgn) • Vậy tổng chi phí của HEAPSORT là O(nlgn) 21
  22. HÀNG ĐỢI ƯU TIÊN • Hàng đợi ưu tiên (priority queue) gồm một tập đối tượng trong đó đối tượng có khoá ưu tiên được xử lý trước • Dùng max-heap để biểu diễn hàng đợi ưu tiên theo khóa lớn hơn • Dùng min-heap để biểu diễn hàng đợi ưu tiên theo khóa nhỏ hơn 22
  23. HÀNG ĐỢI ƯU TIÊN • Thao tác trên hàng đợi ưu tiên . MAX-HEAP-INSERT(A, x) . HEAP-EXTRACT-MAX(A) . HEAP-MAXIMUM(A) . HEAP-INCREASE-KEY(A, x, k) 23
  24. HEAP-EXTRACT-MAX • HEAP-EXTRACT-MAX(A) loại phần tử được ưu tiên nhất ra khỏi hàng đợi A 24
  25. HEAP-EXTRACT-MAX 25
  26. HEAP-EXTRACT-MAX • Thời gian chạy của HEAP-EXTRACT-MAX(A) là O(lg n) trên một heap n phần tử 26
  27. HEAP-INCREASE-KEY • HEAP-INCREASE-KEY(A, i, key) tăng khoá tại nút i lên thành khoá key • Đi chuyển phần tử có khóa key từ nút i hướng đến gốc để tìm nơi chính xác cho nút nhận khoá này 27
  28. HEAP-INCREASE-KEY 28
  29. HEAP-INCREASE-KEY • Thời gian chạy của HEAP-INCREASE-KEY tối đa là O(lg n) trên một heap n phần tử 29
  30. HEAP-INCREASE-KEY 30
  31. MAX-HEAP-INSERT • MAX-HEAP-INSERT(A, key) chèn một phần tử có khoá key vào một max-heap • Đầu tiên, mở rộng heap bằng cách thêm vào một lá mới • Áp dụng HEAP-INCREASE-KEY để tăng khóa key cho nút lá này 31
  32. MAX-HEAP-INSERT 32
  33. MAX-HEAP-INSERT • Thời gian chạy của MAX-HEAP- INSERT tối đa là O(lg n) trên một heap n phần tử 33
  34. QUICKSORT • Mô tả Quicksort • Giải thuật Quicksort • Hiệu suất Quicksort 1
  35. MÔ TẢ QUICKSORT • Do C. A. R Hoare công bố năm 1962 • Là giải thuật tốt, được ứng dụng nhiều trong thực tế 2
  36. MÔ TẢ QUICKSORT • Được thiết kế dựa trên kỹ thuật chia để trị (divide-and- conquer): . Divide: Phân hoạch A[p r] thành hai mảng con A[p q-1] và A[q+1 r] có các phần tử tương ứng nhỏ hơn hoặc bằng A[q ] và lớn hơn A[q] . Conquer: Sắp xếp hai mảng con A[p q-1] và A[q+1 r] bằng lời gọi đệ qui 3
  37. GIẢI THUẬT QUICKSORT 4
  38. PARTITION 5
  39. PARTITION 6
  40. PARTITION • PARTITION luôn chọn phần tử x = A[r] làm phần tử chốt (pivot) để phân hoạch mảng A[ p r] • Khi partition đang thực hiện mảng bị phân hoạch thành bốn vùng 7
  41. PARTITION • Tại điểm bắt đầu của vòng lặp for dòng 3-6 mỗi vùng thoả các tính chất sau đây (bất biến của vòng lặp) . Nếu p k i, thì A[k] x (1) . Nếu i +1 k j -1 , thì A[k] > x (2) . Nếu k = r , thì A[k] = x (3) 8
  42. PARTITION 9
  43. PARTITION • Khởi đầu . Trước lần lặp đầu tiên, i = p -1 và j = p, không có giá trị nào giữa p và i và không có giá trị nào giữa i +1 và j -1 . Các bất biếnvòng lặp thỏa 10
  44. PARTITION • Duy trì . Nếu A[j] > x, thao tác duy nhất trong vòng lặp là tăng j lên 1 , điều kiện 2 thoả cho A[j-1] và tất các mục khác không thay đổi . Nếu A[j] x, i được tăng lên 1, A[i] và A[j] được tráo đổi sau đ ó j tăng lên 1, hệ quả A[i] x và A[j-1 ] > x các bất biến thỏ a 11
  45. PARTITION 12
  46. PARTITION • Kết thúc . Khi j = r, các bất biến vòng lặp thỏa và mảng đã phân hoạch thành ba phần, nhỏ hơn hoặc bằng x , lớ n hơn x và phần cuối chỉ chứa A[r] = x . Hai lệnh kết thúc partition hoán đổi A[r] với phần tử trái nhất l ớn hơn x (vị trí q =i +1) 13
  47. PARTITION • Gọi n = r – p +1 là kích thước đầu vào của PARTITION trên mảng A[ p r] • Thời gian chạy của PARTITION là O(n) 14
  48. HIỆU SUẤTCỦA QUICKSORT • Thời gian chạy của Quicksort phụ thuộc vào partition • Nếu phân hoạch là cân bằng, Quicsort chạy nhanh ít nhất như Heapsort • Trường hợp xấu nhất, thời gian chạy của Quicksort là O(n2) 15
  49. HIỆU SUẤTCỦA QUICKSORT • Trường hợp xấu nhất (worst-case), hai mảng A[p q-1] và A[q+1, r] có thước n -1 và 0 • Chi phí cho PARTITION là O(n) • Vì vậy, thời gian chạy của Quicksort là T(n) = T(n-1) + T(0) + O(n) = O(n2) 16
  50. HIỆU SUẤTCỦA QUICKSORT • Trường hợp tốt nhất (best-case), hai mảng A[p q-1] và A[q+1, r] có thước là n/2 và n/2 -1 • Chi phí cho PARTITION là O(n) • Vì vậy, thời gian chạy của Quicksort là T(n) 2T(n/2) + O(n) = O(nlgn) 17
  51. HIỆU SUẤTCỦA QUICKSORT • Phân hoạch cân bằng (balanced partitioning), hai mảng A[p q- 1] và A[q+1, r] có thướ c xấp xỉ 9n/10 và n/10 • Chi phí cho PARTITION là O(n) • Thơi gian chạy của Quicksort là T(n) T(9n/10) + T(n/10) + O(n) = O(nlgn) 18
  52. HIỆU SUẤTCỦA QUICKSORT Cây đệ qui phân hoạch cân bằng 19
  53. HIỆU SUẤTCỦA QUICKSORT • Trường hợp trung bìmh (average case), Quicksort chạy nhanh gần với trường hợp tốt nhất T(n) = O(nlgn) 20
  54. HIỆU SUẤTCỦA QUICKSORT Hai mức của cây đệ qui cho trường hợp trung bình 21
  55. SẮP XẾP THỜI GIAN TUYẾN TÍNH • Khái niệm • Sắp xếp bằng đếm • Sắp xếp theo lô 1
  56. KHÁI NIỆM • Giải thuật sắp xếp thời gian tuyến tính là giải thuật có thời gian chạy O(n) • Các giải thuật tốt như Heapsort, Quicksort có thời gian chạy O(nlgn) 2
  57. KHÁI NIỆM • Các giải thuật Heapsort, Quicksort dùng phương pháp so sánh, hoán đổi để sắp xếp • Các giải thuật tuyế n tính dựa trên thông tin của các phần tử để sắp xếp nên giảm được bậc của độ phức tạp 3
  58. SẮP XẾP BẰNG ĐẾM • Cho k là một số nguyên, sắp xếp bằng đếm (counting sort) giả sử mỗi một phần tử trong dãy input là một số nguyên trong miền từ 0 đến k 4
  59. SẮP XẾP BẰNG ĐẾM • Ý tưởng là đếm số phần tử nhỏ hơn phần tử x trong mảng nhập để đặ t x trực tiếp vào vị trí của nó trong mảng xuất • Chẳng hạn, nếu có 17 phần tử nh ỏ hơn ho ặc bằng x thì x được đặt vào ví trí 17 5
  60. SẮP XẾP BẰNG ĐẾM // B là mảng xuất kết quả // C là mảng chứa quan hệ các phần tử của A 6
  61. SẮP XẾP BẰNG ĐẾM 7
  62. SẮP XẾP BẰNG ĐẾM • Dòng 1-2 khởi tạo các C[i] = 0 • Dòng 3-4 xác định số phần tử có giá trị là i = A [j] trong A • Dòng 6-7 xác định số phần tử trong A nh ỏ hơn hoặc bằng i, đólàtổng của C[i] và C[i-1] 8
  63. SẮP XẾP BẰNG ĐẾM • Dòng 9-10 đặt A[j] vào trong vị trí được sắp chính xác của nó trong mảng B căn cứ vào số ph ần tử nhỏ hơn hoặc bằng A[j] trong C[A[j]] • Giảm C[A[j]] đi 1 trong dòng 10 để các phần tử còn lại bằng A[j] sẽ được đặt chính xác vào mảng B lần lặp sau 9
  64. SẮP XẾP BẰNG ĐẾM • Chi phí cho lệnh 1-2 là O(k) • Chi phí cho lệnh 3-4 là O(n) • Chi phí cho 6-7 là O(k) • Chi phí cho 9-11 là O(n) . Vì vậ y tổng chi phí thời gian là O(k + n) . Nế u k = O(n) thì tổ ng chi phí là O(n). 10
  65. SẮP XẾP BẰNG ĐẾM • COUNTING-SORT chạy thời gian tuyến tính và hiệu quả hơn các giải thuật sắp xếp bằng so sánh • COUNTING-SORT chỉ sắp xếp các phần tử có khoá trong một miền nhất định (nh ỏ hơn hoặc bằng k cho trướ c) • COUNTING-SORT ph ải sử dụng thêm các mảng trung gian 11
  66. SẮPXẾPTHEO LÔ • Sắp xếp theo lô (Bucket sort) giả sử input là một mảng n số không âm nhỏ hơn 1 12
  67. SẮPP XẾPTHEO LÔ • Ý tưởng của Bucketsort . Phân bố mảng input vào n khoảng con (lô) của khoảng [0, 1) . Sắp xếp các phần tử trong mỗi lô và nố i các lô để có mảng được sắp 13
  68. SẮPXẾPTHEO LÔ // A là mảng mà 0 A[i] <1 // B chứa các lô 14
  69. SẮPXẾPTHEO LÔ 15
  70. SẮPXẾPTHEO LÔ • Xét hai phần tử A[i] và A[j] . Nếu A[i] và A [j] cùng rơi vào một lô, chúng có thứ tự nhờ giải thuật chèn trực tiếp . Ngược lại, gọi các lô tương ứng của A[i] và A[j] là B[i’ ] và B[j’ ], nếu i’ < j’ thì lô B[i’ ] được nối trước lô B[j’ ] và khi đó A[i] A[j] 16
  71. SẮPXẾPTHEO LÔ • Thật vậy, giả sử ngược lại A[i] A[j] thì . i’ = nA[i] nA[j] = j’ . Điều này mâu thuẫn với i’ < j’ , nghĩa là A[i] A[j] • Như vậy, giải thuật đảm bảo th ứ tự củ a mả ng output 17
  72. SẮPXẾPTHEO LÔ • Do phân bố ngẩu nhiên n phần tử vào n khoảng con nên trung bình m ỗi lô có 1 phần tử, vì v ậy thời gian sắp xếp chèn là O(1) • Từ đó, chi phí toàn bộ của giải thuật là O(n) 18
  73. SẮPXẾPTHEO LÔ • BUCKET-SORT chạy thời gian tuyến tính và hiệu quả hơn các giải thuật s ắp xếp bằng so sánh • BUCKET-SORT chỉ sắp xếp các phần tử có khoá trong khoảng [0, 1) • Không phải mọi phân bố sẽ cho mỗi lô chứa 1 phần tử 19
  74. CÁC THUẬTTOÁN ĐỒ THỊ CƠ BảN • Các khái niệm và thuật ngữ • Biểu diễn đồ thị • Tìm kiếm theo chiều rộng • Tìm kiếm theo chiều sâu 1
  75. KHÁI NIỆM VÀ THUẬT NGỮ • Đồ thị vô hướng (undirected graph) G = (V, E), gồm một tập V các đỉnh (vertice) và một tập E các cạnh (edge), mỗi cạnh e = (u, v) E ứng với m ột cặp không có thứ tự các đỉnh u, v V • Đồ thị có hướng (directed graph) G = (V, E), gồm một tập V các đỉnh và một tập E các cạnh, mỗi cạnh e = (u, v) E ứng với một cặp có thứ tự các đỉnh u, v V 2
  76. KHÁI NIỆM VÀ THUẬT NGỮ Ví dụ 1: Đồ thị vô hướng: V = {u, v, x, y, z} E = {e1, e2, e3, e4, e5, e6, e7} e e =(x, y) 1 3 u v e4=(x, y) e5 e7=(z, z) e 2 e z e 3 7 e6 x y e4 3
  77. KHÁI NIỆM VÀ THUẬT NGỮ Ví dụ 2: Đồ thị có hướng: V = {u, v, x, y, z} E = {e1, e2, e3, e4, e5, e6, e7} e e =(x, y) 1 3 u v e4=(y, x) e5 e7=(z, z) e 2 e z e 3 7 e6 x y e4 4
  78. KHÁI NIỆM VÀ THUẬT NGỮ • e7 = (z, z) là cạnh khuyên • e3= (x, y) và e4=(x, y) là hai cạnh song song • Mộ t đồ thị không có cạnh khuyên hoặc cạnh song song gọi là đơ n đồ thị (simple graph), ngược lại gọi là đa đồ thị (multigraph) 5
  79. KHÁI NIỆM VÀ THUẬT NGỮ • Đỉnh u và v là kề nhau (adjacent) nếu có cạnh e =(u, v), cạnh e gọi là liên thuộ c vớ i u và v • Bậ c (degree) của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó, ký hiệu deg(v), đỉnh bậc 0 gọi là đỉnh cô lậ p, đỉnh bậc 1 gọi là đỉnh treo • Bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cạnh đi ra khỏi nó (đi vào nó) và ký hiệu deg+(v) (deg -( v)) 6
  80. KHÁI NIỆM VÀ THUẬT NGỮ Ví dụ 3: Bậc của các đỉnh đồ thị vô hướng e w deg(t)= 1 1 u v deg(z)= 4 deg(w)= 0 e5 e2 e3 z e7 e6 t x y e8 e4 7
  81. KHÁI NIỆM VÀ THUẬT NGỮ Ví dụ 4: Bán bậc của các đỉnh đồ thị có hướng e w deg+(t)= 0 1 u v deg-(t)= 1 deg+(z)= 2 e5 - e2 deg (z)= 2 e3 z e7 e6 t x y e8 e4 8
  82. KHÁI NIỆM VÀ THUẬT NGỮ • Đường đi độ dài n từ đỉnh x0 đến đỉnh xn trong một đồ thị là dãy P = x0, x1 , , xn trong đóm ỗi (xi, xi+1) là một cạnh • Đường đi có đỉnh đầu x0 trùng với đỉnh cuối xn gọi là chu trình • Đường đi hay chu trình g ọi là đơn nếu không có đỉnh lặp lại (trừ đỉnh đầu và cuối nếu là chu trình) 9
  83. KHÁI NIỆM VÀ THUẬT NGỮ Ví dụ 5: P = u, v, z, y là một đường đi và C = u, v, z, y, x, u là m ột chu trình w e1 u v e5 e2 e3 z e7 e6 t x y e8 e4 10
  84. KHÁI NIỆM VÀ THUẬT NGỮ Ví dụ 6: P = x, u, v, z là một đường đi và C = x, y, x là một chu trình w e1 u v e5 e2 e3 z e7 e6 t x y e8 e4 11
  85. KHÁI NIỆM VÀ THUẬT NGỮ • Một đồ thị được gọi là liên thông nếu luôn tìm được đường đ i giữa hai đỉnh bất kỳ của nó 12
  86. KHÁI NIỆM VÀ THUẬT NGỮ Ví dụ 7: Đồ thị là liên thông e1 u v e5 e2 e3 z e6 t x y e8 e4 13
  87. KHÁI NIỆM VÀ THUẬT NGỮ Ví dụ 8: Đồ thị không liên thông u v e4 e2 e3 z e5 t x y e1 14
  88. BIỂU DIỄN ĐỒ THI • Biểu diễn bằng danh sách kề (adjacency list) • Biểu diễn bằng ma trận kề (adjacency matrix) • So sánh các phương pháp biểu diễn đồ thị 15
  89. DANH SÁCH KỀ • Danh sách kề của đỉnh u: adj(u) = {v V | (u, v) E} • Có thể biểu diễn đồ thị G = (V, E) như một tập các danh sách kề bằng cách lư u tr ữ mỗi đỉnh u V cùng với danh sách các đỉnh kề với u 16
  90. DANH SÁCH KỀ Ví dụ 1: Đồ thị vô hướng 1 2 3 nil 1 3 2 1 4 nil 5 3 1 4 5 nil 2 4 4 2 3 5 nil 5 3 4 nil 17
  91. DANH SÁCH KỀ Ví dụ 2: Đồ thị có hướng 1 2 3 nil 1 3 2 nil 5 3 4 5 nil 2 4 4 2 nil 5 4 nil 18
  92. MA TRẬN KỀ • Cho đơn đồ thị G = (V, E), với tập đỉnh V ={1, 2, , n}, ma trận kề của G là A = {aij | i, j =1, 2, , n}, aij = 0 nếu (i, j) E và aij = 1 nếu (i, j) E • Nếu G là đa đồ thị thì aij = 0 nếu (i, j) E và aij = k nếu có k cạnh nối hai đỉnh i và j 19
  93. MA TRẬN KỀ Ví dụ 1: Đồ thị vô hướng 0 1 1 0 0 1 3 1 0 0 1 0 5 1 0 0 1 1 0 1 1 0 1 2 4 0 0 1 1 0 20
  94. MA TRẬN KỀ Ví dụ 2: Đồ thị có hướng 0 1 1 0 0 1 3 0 0 0 1 0 5 0 0 0 1 1 0 0 0 0 0 2 4 0 0 0 1 0 21
  95. MA TRẬN KỀ • Ma trận kề của đồ thị vô hướng đối xứng aij = aji , i, j = 1, 2, 3, , n • Tổng các phầ n tử trên dòng i (cột j) của ma trận kề là bậc của đỉnh i (đỉnh j) 22
  96. MA TRẬN KỀ • Đồ thị có trọng số (weighted graph) là đồ thị mà mỗi cạnh (i, j) đượ c gán một số th ực w(i, j) • Một đồ thị có trọng số với n đỉnh có thể được biểu diễn bởi ma trận trọng s ố C ={cij: i, j =1,2, ,n}, trong đó cij = w(i, j) nếu có cạnh (i, j) và cij = 0, , hoặc - nếu không có cạnh (i, j) 23
  97. MA TRẬN KỀ Ví dụ 3: Ma trận trọng số của đồ thị vô hướng 5 0 10 5 0 0 1 3 12 10 0 6 15 0 6 10 9 5 5 6 0 9 12 0 15 9 0 7 7 2 4 15 0 0 12 7 0 24
  98. SO SÁNH CÁC CÁCH BIỂU DIỄN Biểu diễn đồ thị vô hướng bằng danh sách và ma trận 25
  99. SO SÁNH CÁC CÁCH BIỂU DIỄN Biểu diễn đồ thị có hướng bằng danh sách và ma trận 26
  100. SO SÁNH CÁC CÁCH BIỂU DIỄN • Chi phí bộ nhớ cho ma trận là O(|V|2) và cho danh sách là O(|V|+ 2| E|) • Chi phí xử lý khi dùng ma trận là O(1) và khi dùng danh sách là O|V | 27
  101. TÌM KIẾM THEO CHIỀU RỘNG (Breadth-First Search-BFS) • Thuật toán BFS • Phân tích BFS • Đường đi ngắn nhất 28
  102. THUẬT TOÁN BFS Ý tưởng thuật toán • Bắt đầu tìm kiếm từ đỉnh s cho trước tuỳ ý • Tại thời điểm đã tìm thấy u, thuật toán tiếp tục tìm kiếm tập tất cả các đỉnh kề với u • Thực hiện quá trình này cho các đỉnh còn lại 29
  103. THUẬT TOÁN BFS Ý tưởng thuật toán • Dùng một hàng đợi để duy trì trật tự tìm kiếm theo chiều rộng • Dùng các màu để không lặp lại các đỉnh tìm kiếm • Dùng một mảng để xác định đường đi ngắn nhất từ s đến các đỉnh đã được tìm kiế m • Dùng một mảng để lưu trữ đỉnh đi trước của đỉnh được tìm kiếm 30
  104. THUẬT TOÁN BFS 31
  105. THUẬT TOÁN BFS 32
  106. PHÂN TÍCH BFS • Tổng phí khởi tạo là O(V) • Mỗi thao tác trên hàng đợi là O(1), vì vậy tổng thời gian cho thao tác trên hàng đợi là O(V) • Tổng thời gian chi phí cho quét các danh sách kề là O(E) • Tổng thời gian chạy của BFS là O(V+E) 33
  107. ĐƯỜNG ĐI NGẮN NHẤT • Khoảng cách đường đi ngắn nhất (shortest-path distance) từ s đến v là số cạnh ít nhất trong các đường đi từ s đến v, ký hiệ u (s, v) • Qui ước (s, v) = nếu không có đường đi từ s đến v • Một đường đi độ dài bằng (s, v) từ s đến v được gọi là đường đi ngắn nhất từ s đến v 34
  108. ĐƯỜNG ĐI NGẮN NHẤT • Định lý: Cho BFS chạy trên một đồ thị từ đỉnh s, thì thuật toán tìm kiếm được mọi đỉnh v mà có th ể đạt được từ s, khi kết thúc, BFS xác định các đường đ i ngắn nhất từ s đến v sao cho d[v] = (s, v) với mọi v V 35
  109. ĐƯỜNG ĐI NGẮN NHẤT 36
  110. TÌM KIẾM THEO CHIỀU SÂU (Depth-First Search-DFS) • Thuật toán DFS • Phân tích DFS 37
  111. THUẬT TOÁN DFS Ý tưởng thuật toán • Bắt đầu tìm kiếm từ một đỉnh u nào đó • Chọn đỉnh kề v tùy ý của u để tiếp tục quá trình tìm kiếm và lặp lại quá trình tìm kiếm này đố i với v 38
  112. THUẬT TOÁN DFS Ý tưởng thuật toán • Dùng các màu để không lặp lại các đỉnh tìm kiếm • Dùng các biến thời gian để xác định các thời điểm phát hiện và hoàn thành tìm kiếm của m ột đỉnh • Dùng một mảng để lưu trữ đỉnh đi trước của đỉnh được tìm kiếm 39
  113. THUẬT TOÁN DFS 40
  114. THUẬT TOÁN DFS 41
  115. THUẬT TOÁN DFS 42
  116. PHÂN TÍCH DFS • Nếu chưa tính thời gian thực thi DFS-VISIT, vòng lặp 1-3 và 5-7 có chi phí là O(V) • Trong một lần thực thi DFS-VISIT(u), vòng lặp 4-7 thực thi trong |Adj[u]| lần • Vì u V |Adj[u]|= O(E), nên tổng chi phí thực thi dòng 4-7 của DFS-VISIT là O(E). • Vậy thời gian chạy của DFS là O(V+E) 43
  117. CÂY BAO TRÙM NHỎ NHẤT • Cây và cây bao trùm • Cây bao trùm nhỏ nhất 1
  118. CÂY VÀ CÂY BAO TRÙM • Định nghĩa cây • Các tính chất của cây • Cây bao trùm 2
  119. ĐINH NGHĨA CÂY • Cây tự do (free tree) là một đồ thị vô hướng liên thông không có chu trình (rừng là tập nhiều cây) u v z t x y 3
  120. ĐINH NGHĨA CÂY • Một rừng gồm hai cây u v T1 1 z T2 t x y 4
  121. CÁC TÍNH CHẤT CỦA CÂY • Định lý: Đồ thị T vô hướng n đỉnh là một cây nếu thỏa một trong các điều kiện sau . T không chứa chu trình và có n -1 cạnh . T liên thông và có n -1 cạnh . T liên thông và m ỗ i cạnh của nó đều là cầu . Hai đỉnh bất kỳ được nối với nhau bằng một đường đi duy nhất . T không chứa chu trình nhưng nếu thêm vào một cạnh thì có một chu trình duy nhất 5
  122. CÂY BAO TRÙM • Cây T= (V, F) được gọi là một cây bao trùm (spanning tree) của đồ thị vô hường liên thông G = (V, E) nếu F  E v u v u v u y x y x y x G Cây BT T1 Cây BT T2 6
  123. CÂY BAO TRÙM • Nhận xét . Một đồ thị có thể có nhiều cây bao trùm . Ví dụ đồ thị Kn (gồm n đỉnh và mỗi đỉnh đều có cạnh nối với n-2 n-1 đỉnh còn lại) có n cây bao trùm . Cây bao trùm của G = (V, E) là đồ thị V đỉnh liên thông ít cạnh nhất 7
  124. CÂY BAO TRÙM NHỎ NHẤT • Khái niệm • Thuật giải Kruskal • Thuật giải Prim 8
  125. KHÁI NIỆM • Cho G là một đồ thị vô hướng, liên thông có trọng số và T là một cây bao trùm của G . Trọng số của T, ký hiệu w(T), là tổng trọng số của tất cả các cạnh của nó: w(T) = e T w(e) . Bài toán: Tìm một cây bao trùm T có trọng số nhỏ nhất (minimum spanning tree-MST) của G 9
  126. THUẬT GIẢI KRUSKAL Ý tưởng • Tại mỗi bước, thuật giải tìm một cạnh có trọng số nhỏ nhất thêm vào tập cạnh của cây bao trùm sao cho không gây ra chu trình • Thuật giải dừng khi số cạnh của cây bằng số đỉnh của đồ thị trừ 1 10
  127. THUẬT GIẢI KRUSKAL • Đồ thị G có trọng số và các cạnh được sắp a b c 11 5 14 6 7 9 d 10 4 3 e f g (e, f), (d, g), (c, d), (a, e), (a, f), (b, f), (f, g), (b, c), (c, f) 3, 4, 5, 6, 7, 9, 10, 11, 14 11
  128. THUẬT GIẢI KRUSKAL • Cây bao trùm nhỏ nhất của G a b c 5 6 9 d 10 4 3 e f g (e, f), (d, g), (c, d), (a, e), (b, f), (f, g) 3, 4, 5, 6, 9, 10 12
  129. THUẬT GIẢI KRUSKAL KRUSKAL(G, w) // G =(V, E) có n đỉnh 1. F  // F là số cạnh của cây MST 2. Sort the edges of E into nondecreasing order by weight w 3. while F< n-1 and E // thực hiện cho đến khi F = n-1 hoặc E=  4. do e  x  w(x) = min{w(y), y E)} e có tr ọng số bé nhất 5. E  E-{e} 6. if F {e} not contain cycle then F  F{e} 7. if F< n-1 8. then G is not connected 9. else return T =(V, F) 13
  130. THUẬT GIẢI KRUSKAL • Thời gian sắp xếp là O(E lgE) • Chi phí cho tất cả các lần lặp trong vòng lặp while 3-6 không quá O(V2) • Do đó, tổng chi phí là O(E lg E )+ O(V2) 14
  131. THUẬT GIẢI PRIM Ý tưởng • Khởi đầu, thuật giải chọn một đỉnh bất kỳ của đồ thị làm đỉnh gốc của cây bao trùm bé nhất • Tại mỗi bước chọn thêm một đỉnh của đồ thị mà trọng số cạnh nối nó với một đỉnh của cây là nhỏ nhất • Thuật giải kết thúc khi tất cả các đỉnh của đồ thị đã được chọn 15
  132. THUẬT GIẢI PRIM MST-PRIM(G, w, s) 1. for each u V[G] 2. do key[u]  // key[u] là trọng số nhỏ nhất của cạnh nối u 3. [u]  NIL // với một đỉnh trong cây MSTđang xây dựng 4. key[s] 0 5. Q V[G] 6. while Q  7. do u Extract-min(Q) 8. for each v Adj[u] 9. do if v Q and w(u,v)<key[v] 10. then [v]  u 11. key[v]  w(u,v) 16
  133. THUẬT GIẢI PRIM • Đồ thị G có trọng số, lấy a làm đỉnh xuất phát a b c 11 5 9 14 6 7 d 10 4 3 e f g 17
  134. THUẬT GIẢI PRIM • Key[a]=0, key[u]= với mọi u thuộc V a b c 11 0 5 9 14 6 7 d 10 4 3 e f g 18
  135. THUẬT GIẢI PRIM • Chọn a là đỉnh đầu tiên của MST(do key[a] =0 nhỏ nhất) a b c 11 0 5 9 14 6 7 d 10 4 6 7 3 e f g Cập nhật key[e]=6, key[f]=7 19
  136. THUẬT GIẢI PRIM • Chọn e là đỉnh kế, key[e] =6 a b c 11 0 5 9 14 6 7 d 10 4 6 3 3 e f g Cập nhật key[f]=3 20
  137. THUẬT GIẢI PRIM • Chọn f là đỉnh kế của MST, key[f] =3 a b c 11 0 9 14 5 9 14 6 7 d 10 4 6 3 10 3 e f g Cập nhật key[b]=9, key[c]=14, key[g]=10 21
  138. THUẬT GIẢI PRIM • Chọn b là đỉnh kế của MST, key[b] =9 a b c 11 0 9 11 5 9 14 6 7 d 10 4 6 3 10 3 e f g Cập nhật key[c]=11 22
  139. THUẬT GIẢI PRIM • Chọn g là đỉnh kế của MST, key[g] =10 a b c 11 0 9 11 5 9 14 6 7 4 d 10 4 6 3 10 3 e f g Cập nhật key[d]=4 23
  140. THUẬT GIẢI PRIM • Chọn d là đỉnh kế của MST, key[d] =4 a b c 11 0 9 5 5 9 14 6 7 4 d 10 4 6 3 10 3 e f g Cập nhật key[c]=5 24
  141. THUẬT GIẢI PRIM • Chọn c là đỉnh kế của MST, key[c] =5, kết thúc thuật giải a b c 11 0 9 5 5 9 14 6 7 4 d 10 4 6 3 10 3 e f g 25
  142. THUẬT GIẢI PRIM • Chi phí khởi tạo dòng 1-3 là O(V) • Tổng thời gian cho tất cả các lần gọi EXTRACT-MIN trong vòng lặp while là O(V lg V) • Tổng thời gian cho tất cả các lần lặp của vòng lặp for 8- 11 là O(E lg V) • Do đó, tổng chi phí là O(V lg V + E lg V) = O(E lg V) 26