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

Ths. Phạm Thanh AnBộ môn Khoa học máy tính - Khoa CNTTTrường Đại học Ngân hàng TP.HCMChương 5: ĐỒ THỊMục tiêu của chươngTrì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ánMột số ứng dụng của đồ thịĐịnh nghĩaBostonHartfordAtlantaMinneapolisAustinSFSeattleAnchorageĐị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)abcdeCungĐỉnhCác khái niệmNếu (x,y)  Ex gọi là đỉnh gốc, y là ngọnNếu x ≡ y, (x,y) gọi là khuyênMộ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 tức là có đường đi độ dài 1 từ i tới k và có đường đi đô dài 1 từ k tới jnk=1Bài toán bao đóng truyền ứngTừ đó suy ra A(r) = A Λ A(r-1), R=2, 3,.. Nghĩa là a(r)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.Bài toán bao đóng truyền ứngThuật toán WARSHALLVoid 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])}Bài toán đường đi ngắn nhấtVấn đề Cho một đồ thị định hướng, liên thông, có trọng số GHãy tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong đồ thịThuật toán DijkstraXét đồ thị có hướng G=(V,E), với |V|=nMa trận trọng số d[u,v]≥0, (u,v)EsV là điểm xuất phátH[v]=chiều dài cực tiểu từ s đến v (vV)Thuật toán DijkstraBắt đầu duyệt từ đỉnh sGán giá trị cho H[v]H[v]=d(s,v), nếu (s,v)EH[v]=∞, nếu ngược lạiLặp lại cho đến khi duyệt hết các đỉnhChọn đỉnh w chưa duyệt có H[w] nhỏ nhấtDuyệt đỉnh w nàyVới các đỉnh t chưa duyệt khácH[t] = min(H[t],H[w]+d(w,t))Thuật toán DijkstraHoạt động tốt trên đồ thị trọng số dươngĐộ phức tạp giải thuật là O(n2)Thuật toán DijkstraTìm đường đi từ v0 tới các đỉnh còn lại01 23 4 51023127496sourcenode from node V0 to other nodesV110V25V3V4bestThuật toán Dijkstrastep 1: tìm đường đi ngắn nhất từ 0node 2 được chọn01 23 4 51023127496sourcenode from node V0 to other nodesV110V25V3V4bestV2Thuật toán Dijkstrastep 2: Tính toán lại các đường đi đến tẩt cả các đỉnhTìm đường đi ngắn nhất đến node 0. Node 4 được chọn01 23 4 51023127496sourcenode from node V0 to other nodesV1108V255V314V47bestV2V4Thuật toán Dijkstrastep 2: Tính toán lại các đường đi đến tẩt cả các đỉnhTìm đường đi ngắn nhất từ node 0. node 1 được chọn01 23 4 51023127496sourcenode from node V0 to other nodesV11088V2555V31413V477bestV2V4V1Thuật toán Dijkstrastep 2: Tính toán lại các đường đi đến tẩt cả các đỉnhTìm đường đi ngắn nhất từ node 0. node 3 được chọn01 23 4 51023127496sourcenode from node V0 to other nodesV110888V25555V314139V4777bestV2V4V1V3Thuật toán DijkstraChúng ta có tất cả các đường đi từ v001 23 4 51023127496sourcenode from node V0 to other nodesV1108(0,2)8(0,2)8V25(0,2)555V314(0,2,3)13(0,2,4,3)9(0,2,1,3)V47(0,2,4)77bestV2V4V1V3Q&A