Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 5: Đồ thị - Phạm Thanh An

Nội dung text: Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 5: Đồ thị - Phạm Thanh An

1. Chương 5: ĐỒ THỊ Ths. Phạm Thanh An Bộ môn Khoa học máy tính - Khoa CNTT Trường Đại học Ngân hàng TP.HCM LOGO
2. Mục tiêu của chương ❖Trình bày những kiến thức căn bản về lý thuyết đồ thị, cách biểu diễn, một số thuật toán trên đồ thị ❖Đánh giá thuật toán ❖Một số ứng dụng của đồ thị
3. Định nghĩa Anchorage Boston Minneapolis Seattle Hartford SF Austin Atlanta
4. Định nghĩa ❖Đồ thị G = (V,E) ▪ V = tập hợp hữu hạn các phần tử (đỉnh hay nút) ▪ E  V × V, tập hữu hạn các cạnh (cung) a b Đỉnh c Cung d e
5. Các khái niệm ❖ Nếu (x,y) E • x gọi là đỉnh gốc, y là ngọn • Nếu x ≡ y, (x,y) gọi là khuyên ❖ Một dãy u1,u2, ,un, ui V (i=1,n) gọi là một đường, nếu (ui-1,ui) E ❖ Độ dài đường: length(u1,u2, ,un)=n ❖ (u1,u2, ,un) đường đi đơn, nếu ui≠uj, 1<i≠j<n (là đường đi, mà các đỉnh phân biệt, ngoại trừ đình đầu và đỉnh cuối)
6. Các khái niệm (tt) ❖Chu trình (cycle) = (u1,u2, ,un), u1≡ un ❖Đồ thị định hướng (directed graph) ▪ (x,y) E : (x,y) ≠ (y,x) ❖Đồ thị vô hướng ▪ (x,y) E : (y,x) E ▪ (x,y) ≡ (y,x)
7. Các khái niệm (tt) ❖CBDC là một chu trình B B A C A C Đường đi đơn D D Chu trình
8. Các khái niệm (tt) Đồ thị vô hướng Đồ thị định hướng
9. Các khái niệm (tt) ❖Tính liên thông (connectivity) ▪ Trong đồ thị G, hai đỉnh x,y gọi là liên thông (connected), nếu có một đường từ x đến y ▪ Đồ thị G liên thông, nếu (x,y) E,  đường đi từ x đến y ❖Đồ thị G gọi là có trọng số, nếu mỗi cung được gán một giá trị số đặc trưng
10. Các khái niệm (tt) Đồ thị liên thông Đồ thị không liên thông
11. Các khái niệm (tt) ❖Đồ thị có trọng số 0 10 20 1 1 2 4 5 3
12. Biểu diễn đồ thị ❖Biểu diễn bằng ma trận kề ▪ Adjacency matrice ❖Biểu diễn bằng danh sách kề ▪ Adjacency list
13. Biểu diễn bằng ma trận kề ❖Xét G=(V,E) với V={x1, ,xn} ❖Biểu diễn G bằng ma trận A=(aij), i,j=1 n ▪ aij=1, nếu Ǝ (xi,xj) E ▪ aij=0, nếu !Ǝ (xi,xj) E
14. Biểu diễn bằng ma trận kề(tt) A[i][j] 0 1 2 3 0 0 0 1 1 0 1 1 0 1 1 1 2 1 1 0 1 2 3 0 1 1 0 3 0 1 1 0 1 0 1 1 A = 1 1 0 1 0 1 1 0
15. Biểu diễn bằng ma trận kề(tt) A[i][j] 0 1 2 3 0 0 1 1 1 0 1 0 0 0 1 2 0 0 0 1 1 2 3 0 0 0 0 3 0 1 1 1 A = 0 0 0 1 0 0 0 1 0 0 0 0
16. Biểu diễn bằng ma trận kề(tt) x2 0 1 1 0 0 0 0 0 0 1 x1 x3 0 1 0 0 0 0 0 1 0 0 x x5 4 1 0 0 1 0
17. Biểu diễn bằng ma trận kề (tt) x2 0 1 1 0 0 0 0 0 1 1 x1 x3 0 1 0 0 0 0 1 1 0 0 x x5 4 1 0 0 1 1
18. Biểu diễn bằng ma trận kề (tt) A[i][j] 0 1 2 3 0 0 20 10 1 1 20 0 0 5 0 20 2 10 0 0 4 10 3 1 5 4 0 1 1 2 5 0 20 10 1 4 20 0 0 5 3 A = 10 0 0 4 1 5 4 0
19. Biểu diễn bằng ma trận kề (tt) ❖Chú ý ▪ Đối với đồ thị không định hướng, ma trận kề là ma trận đối xứng ▪ Đối với đồ thị định hướng, số lượng phần tử 0 khá lớn ▪ Đối với đồ thị có trọng số, thay thế giá trị 1 bằng giá trị trọng số
20. Biểu diễn đồ thị bằng danh sách kề ❖Là một mảng các danh sách ❖Ở đây, n hàng của ma trận kề thay thế bằng n danh sách liên kết động ❖Mỗi đỉnh của G có một danh sách, mỗi nút trong danh sách thể hiện các đỉnh lân cận của nút này ▪ Cấu trúc mỗi nút • id: tên đỉnh (chỉ số, danh hiệu) • next: con trỏ đến nút kế tiếp
21. Biểu diễn đồ thị bằng danh sách kề (tt) 0 1 2 3 0 1 3 1 2 3 2 3 3
22. Biểu diễn đồ thị bằng danh sách kề (tt) x 2 x[1] 2 3 x1 x3 x[2] 5 x[3] 2 x[4] 3 x x4 5 x[5] 1 4
23. Biểu diễn đồ thị bằng danh sách kề (tt) 0 0 1 10 2 20 3 1 10 20 1 0 10 3 4 1 1 2 2 0 20 3 5 4 5 3 3 0 1 1 4 2 5
24. Biểu diễn đồ thị bằng danh sách kề (tt) ❖Chú ý ▪ Các nút đầu danh sách được lưu vào một mảng (truy cập nhanh) ▪ Với đồ thị không định hướng có n đỉnh và e cạnh, thì cần n nút đầu và 2e nút ‘trong’ danh sách ▪ Với đồ thị định hướng có n đỉnh và e cạnh, thì chỉ cần e nút ‘trong’ danh sách ▪ Thứ tự các nút không quan trọng
25. Phép duyệt đồ thị ❖Từ một đỉnh, liệt kê tất cả các đỉnh của đồ thị ▪ Phép tìm kiếm theo chiều sâu • Depth first search ▪ Phép tìm kiếm theo chiều rộng • Breadth first search
26. Phép tìm kiếm theo chiều sâu ❖Ý tưởng ▪ Tại đỉnh v bất kỳ, duyệt đỉnh v, và xét tập các đỉnh đến được từ đỉnh v ▪ Lập lại thao tác trên đối với đỉnh w bất kỳ trong tập các đỉnh từ v nói trên
27. Phép tìm kiếm theo chiều sâu (tt) x2 x1 x3 x43 x4 x3251 x5 x12
28. Phép tìm kiếm theo chiều sâu (tt) ❖Nhận xét ▪ Thời gian thực hiện giải thuật ~ (n+e), nếu G được biểu diễn bằng danh sách kề ▪ Thời gian thực hiện giải thuật ~ n2, nếu G được biểu diễn bằng ma trận kề ▪ Giải thuật này sử dụng để chứng minh một đồ thị có liên thông hay không
29. Phép tìm kiếm theo chiều rộng ❖ Tại điểm v bất kỳ, duyệt đỉnh v, thu được tập hợp W gồm các đỉnh w xuất phát từ v ❖ Lặp lại thao tác trên đối với tất cả các đỉnh w trong W, thu được tập hợp đỉnh Z ❖ Lặp lại thao tác trên đối với tất cả các đỉnh z trong Z ❖ Lặp lại cho đến khi tất cả mọi đỉnh đều được duyệt qua ít nhất một lần
30. Phép tìm kiếm theo chiều rộng(tt) x1 x2 x3 x5 x2 x1 x4 x2 x1 x3 x4 x5
31. Phép tìm kiếm theo chiều rộng(tt) ❖Nhận xét ▪ Thời gian thực hiện giải thuật ~ (n+e), nếu G được biểu diễn bằng danh sách kề ▪ Thời gian thực hiện giải thuật ~ n2, nếu G được biểu diễn bằng ma trận kề
32. Cây khung (Spanning tree) ❖T=(V,E’)  G=(V,E), với E  E’ bao gồm các cung thuộc một phép duyệt từ một đỉnh đến các đỉnh còn lại trong V ❖Giá của cây khung T = tổng trọng số của các cung thuộc E’ Cây khung T Đồ thị G của đồ thị G
33. Cây khung (Spanning tree) ❖Chú ý ▪ Một đồ thị G có thể có nhiều cây khung ▪ Cây khung theo chiều rộng, theo chiều sâu ▪ Các cung trong cây khung không tạo nên chu trình • Giữa hai đỉnh trong một cây khung chỉ tồn tại duy nhất một đường đi từ đỉnh này đến đỉnh kia ▪ Nếu đồ thị có n đỉnh, thì cây khung có n-1 cạnh
34. Cây khung cực tiêu ❖ Là cây khung với tổng các trọng số là cực tiểu 6 6 10 10 1 7 1 20 5 5
35. Thuật toán Kruskal ❖Sắp xếp các cung theo thứ tự không giảm đối với trọng số ❖Bắt đầu từ T=Ø ❖Lặp cho đến khi ko còn đỉnh nào ( |E’| = n-1) ▪ lấy ra cung w có trọng số nhỏ nhất ▪ thêm cung w vào T với điều kiện không tạo chu trình trong T
36. Cây khung (Spanning tree) ❖Ví dụ: Cho một đồ thị G vô hướng, liên thông, có trọng số. Hãy tìm cây khung cực tiểu của G x 9 x2 x6 x1 x3 x7 x 8 x x5 4
37. Thuật toán Kruskal ❖Để kiểm tra xem có tạo ra chu trình trong T hay không, chúng ta xem hai đỉnh của cung được thêm có thuộc tập các đỉnh hiện có trong T không, nếu có, nghĩa là sẽ tạo nên chu trình
38. Bài toán bao đóng truyền ứng ❖Cho đồ thị G = (V,E) ▪ Có tồn tại đường đi giữa hai nút x và y trong đồ thị G hay không? ▪ Bài toán này có thể giải được dễ dàng bằng cách sử dụng ma trận kề của đồ thị
39. Bài toán bao đóng truyền ứng ❖Ma trận kề A của đồ thị G=(V,E) ▪ aij=true, nếu Ǝ (xi,xj) E ▪ aij=false, nếu ngược lại ❖Phép cộng A=(aij), B=(bij) ▪ A V B = C, với cij=aij V bij ❖Phép nhân A=(aij), B=(bij) ▪ D =A Λ B, với dij=V(aiknΛbkj) Với 1<=i, j, <=n k=1
40. Bài toán bao đóng truyền ứng ❖Với ma trận A, nếu aij =1, có nghĩa là có một cung từ i tới j. ❖Xét A(2) = A Λ A. Rõ ràng nếu phần tử ở hàng i, cột j của A(2) bằng 1, thì có ít nhất có một đường đi có độ dài 2, từ đỉnh i đến đỉnh j, vì (2) a ij = V (aik Λ akj) n ▪ aik Λ akj =1, khi aik =1 và akj =1, => tức là có đườngk=1 đi độ dài 1 từ i tới k và có đường đi đô dài 1 từ k tới j
41. Bài toán bao đóng truyền ứng ❖Từ đó suy ra A(r) = A Λ A(r-1), R=2, 3, (r) Nghĩa là a ij = 1, thì có ít nhất 1 đường đi đô dài r, từ i tới j. ❖Ta lập ma trân P = A V A(2) V V A(n) ❖ Thì P sẽ cho biết có hay không một đường đi có độ dài lớn nhất là n, từ đỉnh i tới j. P được gọi là ma trận đường đi.
42. Bài toán bao đóng truyền ứng ❖Thuật toán WARSHALL Void WARSHALL(A, P, n){ For (int k=0;k<n;k++) For (int i=0;i<n;i++) For (int j=0;j<n;j++) P[i,j]=P[i,j] V (P[i,k] Λ P[k,j]) }
43. Bài toán đường đi ngắn nhất ❖Vấn đề ▪ Cho một đồ thị định hướng, liên thông, có trọng số G ▪ Hãy tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong đồ thị
44. Thuật toán Dijkstra ❖Xét đồ thị có hướng G=(V,E), với |V|=n ❖Ma trận trọng số d[u,v]≥0, (u,v) E ❖s V là điểm xuất phát ❖H[v]=chiều dài cực tiểu từ s đến v (v V)
45. Thuật toán Dijkstra ❖ Bắt đầu duyệt từ đỉnh s ❖ Gán giá trị cho H[v] ▪ H[v]=d(s,v), nếu (s,v) E ▪ H[v]=∞, nếu ngược lại ❖ Lặp lại cho đến khi duyệt hết các đỉnh ▪ Chọn đỉnh w chưa duyệt có H[w] nhỏ nhất ▪ Duyệt đỉnh w này ▪ Với các đỉnh t chưa duyệt khác • H[t] = min(H[t],H[w]+d(w,t))
46. Thuật toán Dijkstra ❖Hoạt động tốt trên đồ thị trọng số dương ❖Độ phức tạp giải thuật là O(n2)
47. Thuật toán Dijkstra ❖Tìm đường đi từ v0 tới các đỉnh còn lại from node V to other 1 node 0 1 3 nodes 10 2 3 V 10 0 9 4 6 1 source V2 5 5 7 2 4 V 2 3 V4 best
48. Thuật toán Dijkstra step 1: tìm đường đi ngắn nhất từ 0 ◼ node 2 được chọn from node V to other 1 node 0 1 3 nodes 10 2 3 V 10 0 9 4 6 1 source V2 5 5 7 2 4 V 2 3 V4 best V2
49. Thuật toán Dijkstra step 2: Tính toán lại các đường đi đến tẩt cả các đỉnh ◼ Tìm đường đi ngắn nhất đến node 0. Node 4 được chọn from node V to other node 0 nodes 1 1 3 10 V1 10 8 2 3 9 0 4 6 V2 5 5 source 5 7 V3 14 2 4 2 V4 7 best V2 V4
50. Thuật toán Dijkstra step 2: Tính toán lại các đường đi đến tẩt cả các đỉnh ◼ Tìm đường đi ngắn nhất từ node 0. node 1 được chọn from node V to other node 0 1 nodes 1 3 10 V1 10 8 8 2 3 0 9 4 6 V2 5 5 5 source 7 5 V3 14 13 2 4 2 V4 7 7 best V2 V4 V1
51. Thuật toán Dijkstra step 2: Tính toán lại các đường đi đến tẩt cả các đỉnh ◼ Tìm đường đi ngắn nhất từ node 0. node 3 được chọn from node V to other node 0 nodes 1 1 3 10 V1 10 8 8 8 2 3 0 9 4 6 V2 5 5 5 5 source 7 5 V3 14 13 9 2 4 2 V4 7 7 7 best V2 V4 V1 V3
52. Thuật toán Dijkstra ❖ Chúng ta có tất cả các node from node V0 to other nodes đường đi từ v 0 8 8 V 10 8 1 (0,2) (0,2) 1 1 3 5 10 V 5 5 5 2 (0,2) 2 3 9 0 4 6 14 13 9 source V3 (0,2,3 (0,2,4, (0,2,1, 5 7 ) 3) 3) 2 4 2 7 V4 (0,2,4 7 7 ) best V2 V4 V1 V3