Bài giảng Cấu trúc dữ liệu và giải thuật - Đồ thị và các thuật toán trên đồ thị

Đồ thị và các thuật toán trên đồ thịKhái niệmĐường đi ngắn nhấtĐường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại của đồ thị GĐường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thịCây bao trùm ngắn nhất11. Khái niệmX là một tập hữu hạn và không rỗng các phần tử nào đó và U  X x X. G = (X,U) gọi là đồ thị hữu hạn.Mỗi phần tử x  X gọi là một đỉnh của đồ thịMỗi phần tử u =(x,y)  U gọi là một cạnh của đồ thịX gọi là tập các đỉnh, U gọi là tập các cạnh21. Khái niệm (tiếp)G = (X,U) là đồ thị vô hướng nếu với mọi cạnh u=(x,y)  U không phân biệt thứ tự các đỉnh x và y, tức là từ x đến y không kể hướng, hay (x,y) = (y,x)G = (X,U) là đồ thị có hướng nếu với mọi cạnh u=(x,y)  U có phân biệt thứ tự các đỉnh x và y, có hướng x đến y, hay (x,y)  (y,x)31. Khái niệm (tiếp)Cho G = (X,U) và u =(x,y)  U là một cạnh nối đỉnh x và y. Khi đó ta nói u là cạnh chứa đỉnh x,y hoặc x,y là các đỉnh thuộc cạnh u. Khi đó x,y được gọi là hai đỉnh kề nhauHai cạnh kề nhau nếu giữa chúng có đỉnh chung.Ví dụ với u=(x,y) và v =(y,z) thì u,v là hai cạnh kề nhau 41. Khái niệm (tiếp)Đồ thị G = (X,U) gọi là đồ thị đơn nếu giữa hai đỉnh bất kỳ được nối với nhau bởi không quá một cạnhĐồ thị G = (X,U) gọi là đa đồ thị nếu nó có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh trở lên51. Khái niệm (tiếp)Nếu trong đồ thị ta bỏ đi một số đỉnh nào đó và các cạnh chứa đỉnh đó thì phần còn lại của đồ thị được gọi là đồ thị con của đồ thị đã cho.Nếu trong đồ thị ta bỏ đi một số cạnh giữ nguyên các đỉnh thì phần còn lại của đồ thị được gọi là đồ thị bộ phận của đồ thị đã cho.61. Khái niệm (tiếp)x1x2x3x4x5X1 và X2 là hai đỉnh kề nhauX2 và X3 là hai đỉnh kề nhauX1 và X4 là hai đỉnh kề nhau71. Khái niệm (tiếp)x1x2x4x581. Khái niệm (tiếp)x1x2x3x4x591. Khái niệm (tiếp)G = (X,U) là đồ thị vô hướng (hoặc có hướng). Một đường đi trong đồ thị là một dãy x1ui1x2ui2 xikuikxik+1, trong đó các xij là các đỉnh còn các uịj là các cạnh sao cho với  j  {1,2 ,k} thì đỉnh xij và đỉnh xij+1 là hai đỉnh kề nhau.Chu trình trong đồ thị là một đường đi có đỉnh xuất phát và đỉnh kết thúc trùng nhau.102. Biểu diễn đồ thị (tiếp)Biểu diễn hình họcBiểu diễn bằng ma trận kề112.1. Biểu diễn hình họcMỗi đỉnh x  X ta đặt tương ứng với mỗi điểm trên một mặt phẳng.Với G =(X,U) là đồ thị vô hướng. Trong trường hợp này nếu u =(x,y)  U thì trong mặt phẳng, các đỉnh x và đỉnh y được nối với nhau bởi một cạnh không có hướngNếu (x,x)  U thì tại đỉnh x sẽ có một khuyên122.1. Biểu diễn hình học tiếp)x1x2x4x5x7x6132.1. Biểu diễn hình học (tiếp)Mỗi đỉnh x  X ta đặt tương ứng với mỗi điểm trên một mặt phẳng.Với G =(X,U) là đồ thị có hướng. Trong trường hợp này nếu u =(x,y)  U thì trong mặt phẳng sẽ có một cung có hướng đi từ đỉnh x đến đỉnh y Nếu (x,x)  U thì tại đỉnh x sẽ có một khuyên có hướng vào chính nó142.1. Biểu diễn hình học (tiếp)x1x2x4x5x7x6152.2. Biểu diễn bằng ma trận kềG =(X,U) là đồ thị vô hướng với X = {x1,x2, , xn}. Đồ thị G có thể biểu diễn bằng ma trận kề vuông cấp n mà phần tử aij ở hàng i cột j được xác đinh như sau:aịj = d nếu giữa cặp đỉnh xi và xj có d cạnhaij = 0 nếu cặp đỉnh xi và xj không được nối với nhau162.2 Biểu diễn bằng ma trận kề (tiếp)G =(X,U) là đồ thị có hướng với X = {x1,x2, , xn}. Đồ thị G có thể biểu diễn bằng ma trận kề vuông cấp n mà phần tử aij ở hàng i cột j được xác đinh như sau:aịj = d nếu giữa cặp đỉnh xi và xj có d cạnh từ xi đến xjaij = 0 nếu cặp đỉnh xi và xj không được nối với nhau 172.2 Biểu diễn bằng ma trận kề (tiếp)x1x2x3x40 1 0 01 0 1 20 1 0 00 2 0 0 183. Đường đi ngắn nhấtĐồ thị có trọng số:	Đó là các đồ thị mà mỗi cạnh (u,v) được gắn với một số c(u,v). Số c(u,v) được gọi là trọng số của cung nó được gọi là giá hoặc độ dài của cạnh (u,v)Đồ thị liên thông:Cho đồ thị G =(X,U). Hai đỉnh phân biệt x,y  X được gọi là liên thông nếu tồn tại một đường đi nối các đỉnh x,y với nhau.Đồ thị G gọi là liên thông nếu với hai đỉnh phân biệt bất kỳ trong đồ thị đều là liên thông193. Đường đi ngắn nhất (tiếp)Tìm đường đi ngắn nhất từ một đỉnh nguồn tới các đỉnh các đỉnh còn lại của đồ thịTìm đường đi ngắn nhất giữa một cặp đỉnh của đồ thị203. Đường đi ngắn nhất từ một đỉnh nguồn - Thuật toán Dijkstra (tiếp)Bài toán:Cho đồ thị G =(X,U) đơn liên thông có trọng sốTìm đường đi ngắn nhất từ đỉnh nguồn X đến tất cả các đỉnh còn lại. Các đỉnh x được đánh số 1 tới nĐồ thị được biểu diễn bởi ma trận kề C[1..n,1..n], trong đó C[i,j] là độ dài cung (i,j) nếu không có cung (i,j) thì C[i,j] = 213. Đường đi ngắn nhất từ một đỉnh nguồn - Thuật toán Dijkstra (tiếp)1234510110462022223. Đường đi ngắn nhất từ một đỉnh nguồn - Thuật toán Dijkstra (tiếp)1234510110462022Tìm đường đi từ đỉnh 1 đến các đỉnh còn lạiĐường đi : 1,5,4,2Độ dài : 2+2+4 = 8 Đường đi : 1,2Độ dài : 10Đường đi : 1,3,2Độ dài : 6+1 =7The best !!!233. Đường đi ngắn nhất từ một đỉnh nguồn - Thuật toán Dijkstra (tiếp)1234510110462022Tìm đường đi từ đỉnh 1 đến 3Đường đi : 1,3Độ dài : 6243. Đường đi ngắn nhất từ một đỉnh nguồn - Thuật toán Dijkstra (tiếp)1234510110462022Tìm đường đi từ đỉnh 1 đến 4Đường đi : 1,4Độ dài : 20Đường đi : 1,3,4Độ dài : 6+10 =16Đường đi : 1,5,4Độ dài : 2+2 =4253. Thuật toán Dijkstra (tiếp) – Giải thuậtGán trọng số các đỉnhTrọng số của đỉnh xuất phát là t(a) = 0Tại các đỉnh còn lại ta ghi một trọng số dương t đủ lớn sao cho giá trị t này lớn hơn trọng số của các đỉnh từ a tới.263. Thuật toán Dijkstra (tiếp) – Giải thuậtThực hiện việc giảm trọng số các đỉnhGiả sử tại đỉnh x có trọng số t(x)Nếu tồn tại đỉnh y có trọng số t(y) từ y đến x mà t(x) > t(y) + l(y,x) thì ta thay trọng số t(x) bởi trọng số t’(x) = t(y) + l(y,x)Trong trường hợp t(x) 2 : qua đỉnh 3 Độ dài 71->3: Độ dài 61->4 : qua đỉnh 5 Độ dài 41->5: Độ dài 2313. Thuật toán Dijkstra (tiếp) – Giải thuậtDisjktra;S = {1};For i = 2 to n do D[i] = C[1,i];P[i]=1;While X-S   doChọn x  X- S mà D[x] nhỏ nhất;S =S  {x}For y  X- S doIf D[x] +C[x,y] = 0G’ = (X,U’) là cây bao trùm của GĐộ dài của cây G’ được xem là tổng trọng số của các cạnh tạo thành G’Tìm G’ của G sao cho G’ có độ dài ngắn nhất55Thuật toán PrimCho G =(X,U) là đồ thi mà mỗi cạnh u thuộc U có trong số l(u)>=0Xác định cạnh có trọng số bé nhất trong tất cả các cạnh trong U. Giả sử là u1Giả sử u2 là cạnh có trọng số bé nhất trong các cạnh U \ {u1}Giả sử u3 là cạnh có trọng số bé nhất trong các cạnh U \{u1,u2}. Với điều kiện {u1,u2,u3} không tạo thành chu trình56Thuật toán Prim (tiếp).Giả sử bước k ta đã xác định được {u1,u2,u3,,uk} có trọng số bé nhất và không tạo thành chu trìnhThực hiện bước n-1 thì dừng lại. Khi đó ta có {u1,u2,u3,,un-1} không tạo thành chu trình và có trọng số bé nhất. Khi đó ta có G’ =(X,Un-1) là cây bao trùm bé nhất của G cần tìm57Thuật toán Prim (tiếp)12354617628435391235461235358Thuật toán Prim (tiếp)Cho đồ thị G = (X,U)Gọi X’ là tập các đỉnh kề các cạnh trong G’Ban đầu X chứa một đỉnh tuỳ ý trong G giả sử x, tập các cạnh G’ rỗngỞ mỗi bước ta chọn cạnh (x,y) ngắn nhất sao cho x X’ và y  X-X’. Thêm y vào X’ và thêm (x,y) vào G’Tiếp tục phát triển G’ cho đến khi X’ =X. Khi đó G’ trở thành cây bao trùm ngắn nhất của G59Thuật toán Prim (tiếp)X ={x} (x: đỉnh tuỳ ý thuộc X)G =Thực hiện các bước sau cho đến khi X’=XChọn cạnh (x,y) có trọng số nhỏ nhất với x  X’, y  X-X’X’ = X’  {x}G’ =G’  {(x,y) }60Thuật toán Prim (tiếp)1235461762843539BướcX’(x,y)Khởi tạo{1}-1{1,4}(1,4)2{1,4, 5}(1,5)3{1,4, 5, 3}(5,3)4{1,4, 5, 3, 2}(3, 2)5{1,4, 5, 3, 2, 6}(3, 6)61Thuật toán Prim (tiếp)1235461762843539BướcX’(x,y)Khởi tạo{3}-1{3, 2}(3, 2)2{3, 2, 6}(3, 6)3{3, 2, 6,5}(3, 5)4{3, 2, 6, 5, 1}(5, 1)5{3, 2, 6, 5, 1, 4}(1,4)62Thuật toán Prim (tiếp)- Bài tập312356135461Tìm cây bao trùm ngắn nhất của đồ thị G63Thuật toán Prim (tiếp)- Bài tậpTìm cây bao trùm ngắn nhất của đồ thị Gabcdefghiklm231112233333344464Câu hỏi ôn tập phần Giải thuậtKhái niệm thuật toán ?Các phương pháp biểu diễn thuật toán?Trình bày phương pháp Chia để trị? (Ý tưởng, phương pháp, lược đồ tổng quát)Trình bày giải thuật bài toán tìm kiếm nhị phân trên dãy đã được sắp, viết chương trình (C++, hoặc Pascal)Trình bày phương pháp Tham lam? (Ý tưởng, phương pháp, lược đồ tổng quát)65Câu hỏi ôn tập phần Giải thuậtTrình bày phương pháp Quay lui (Ý tưởng, phương pháp, lược đồ tổng quát)Trình bày giải thuật bài toán Tám hậu, Mã đi tuần, Liệt kê các hoán vị của nViết chương trình (C++ hoặc Pascal) bài toán Liệt kê các hoán vị của nTrình bày thuật toán Dijkstra. Viết chương trình (C++ hoặc Pascal) Trình bày thuật toán FloydTrình bày thuật toán Prim66