Cấu trúc dữ liệu và giải thuật - Chương 6: Đồ thị

CHƯƠNG 6ĐỒ THỊ1Chương 6: Đồ thị6.1 Định nghĩa và các khái niệm6.2 Biểu diễn đồ thị6.3 Phép duyệt đồ thị6.4 Tìm đường đi ngắn nhất2Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó .Nhiều bài toán thuộc những lĩnh vực rất khác nhau có thể giải được bằng mô hình đồ thị: biểu diễn sự cạnh tranh các loài trong một môi trường sinh thái, hai máy tính có được nối với nhau bằng một đường truyền thông hay không. tìm đường đi ngắn nhất giữa hai thành phố, lập lịch thi, phân chia kênh cho các đài truyền hình 6.1-Định nghĩa và khái niệm3Khi mô hình hoá bằng đồ thị: đỉnh biểu thị các đối tượng được xem xét (người, tổ chức, địa danh,...), cạnh đồ thị là những đoạn thẳng (hoặc cong) hay những mũi tên nối một số điểm với nhau, tượng trưng cho một quan hệ nào đó giữa các đối tượng.Các loại đồ thị :Một đơn đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E là các cạnh gồm các cặp không có thứ tự của các đỉnh phân biệt.6.1-Định nghĩa và khái niệm4Một đơn đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E các cặp có thứ tự gồm 2 phần tử khác nhau của V gọi là các cung.Một đa đồ thị G = (V, E) giống như đơn đồ thị, có thể có cạnh bội (có nhiều hơn hai cạnh tương ứng với một cặp đỉnh) và khuyên (cạnh nối đỉnh với chính nó).6.1-Định nghĩa và khái niệm5v3v4v5v6v1v26.1-Định nghĩa và khái niệm6Các thuật ngữ về đồ thị :Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi là liền kề nếu (u,v)E. Nếu e = (u,v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e.Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số các cạnh liên thuộc với nó. Khuyên tại một đỉnh được tính hai lần cho bậc của nó.Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)=0 6.1-Định nghĩa và khái niệm7v1v2v3v4v5v6v76.1-Định nghĩa và khái niệm8Bậc vào (t.ư. bậc ra) của đỉnh v trong đồ thị có hướng G, ký hiệu degt(v) (t.ư. dego(v)), là số các cung có đỉnh cuối (đỉnh đầu) là v.Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô lập. Đỉnh có bậc vào bằng 1 và bậc ra bằng 0 gọi là đỉnh treo, cung có đỉnh cuối là đỉnh treo gọi là cung treoCho G =(V, E) là một đồ thị có hướng. Khi đó 6.1-Định nghĩa và khái niệm9621. Ma trận kề: Cho đồ thị vô hướng G=(V,E), v1, v2, ..., vn là các đỉnh và e1, e2, ..., em là các cạnh của G. Ma trận kề của G là ma trậnaij bằng 1 nếu cạnh (i,j) E và bằng 0 nếu ngược lại. Rõ ràng ma trận kề của đồ thị vô hướng là đối xứng.Ngoài ra, aij có thể gán một số nào đó gọi là trọng số. Lúc đó, ta có ma trận trọng số.Nhược điểm là luôn phải dùng n2 đơn vị bộ nhớ để lưu trữ ma trận kề.6.2- Biểu diễn đồ thị10Ví dụ: Ma trận kề của đồ thị v1v2v3v4v5e1e2e3e4e5e66.2- Biểu diễn đồ thị11622. Danh sách kề: Mỗi đỉnh v của đồ thị có danh sách lưu trữ các đỉnh kề với nó, ký hiệu Ke(v):Ke(v)={ uV: (v,u)E}Người ta có thể dùng mảng hoặc danh sách liên kết cho Ke(v). Chúng ta phải dùng m+n đơn vị bộ nhớ để lưu trữ danh sách kề.6.2- Biểu diễn đồ thịv1v2v3v4v5e1e2e3e4e5e612Tìm kiếm theo chiều sâu: void main(){ for v  V do chuaxet[v]:=true; for v  V do if (chuaxet[v]) then DFS(v);}void DFS(v){ thamdinh(v); chuaxet[v]:=false; for u  Ke(v) do if (chuaxet[u]) DFS(u);}6.3- Duyệt đồ thị1337121045986111312Kết quả tìm kiếm theo chiều sâu: 1, 2, 10, 4, 3, 5, 8, 6, 7, 9, 12, 11, 13 6.3- Duyệt đồ thị14Đặc điểm:Mỗi đỉnh được thăm đúng 1 lần.Mỗi lần quay về chương trình chính, thuật toán se tạo ra một thành phần liên thông mới.Độ phức tạp của thuật toán là O(n+m).6.3- Duyệt đồ thị15Tim kiem theo chieu rong: void main(){ for (v  V) chuaxet[v]:=true; for (v  V) do if (chuaxet[v]) BFS(v);}6.3- Duyệt đồ thị16void BFS(v){ Queue:=; Queue  v; (*nap v vao Queue *) chuaxet[v]:=false; while (Queue ≠ ) { p  Queue; thamdinh(p); for (u  Ke(p)) if (chuaxet[u]) {Queue  u; chuaxet(u):=false;} }}6.3- Duyệt đồ thị17Đường đi độ dài n từ đỉnh u đến đỉnh v, với n là một số nguyên dương trong đồ thị G=(V,E) là một dãy các cạnh (hoặc cung) e1, e2, ..., en của đồ thị sao cho e1=(x0,x1),e2=(x1,x2), ...,en=(xn-1,xn), với x0=u và xn=v. Trong đồ thị đơn, ta ký hiệu đường đi này bằng dãy các đỉnh x0, x1, ..., xn.Nếu mỗi cung được đặt tương ứng một số thực a(xi,xj) gọi là trọng số, lúc đó độ dài đường đi là:a(xi-1,xj) với i=1 đến n6.4- Đường đi ngắn nhất18Thuật toán Dijkstra:-Đầu vào: Đồ thị G=(V,E) biểu diễn bằng ma trận trọng số a[u,v] với u,v  V-Điều kiện: a[u,v] >= 0-Đầu ra: Khoảng cách từ đỉnh s (đỉnh bắt đầu cho trước) đến tất cả các đỉnh còn lại ký hiệu d[v]. truoc[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v.-Ký hiệu: T là tập hợp chứa các đỉnh có nhãn tạm thời.6.4- Đường đi ngắn nhất19void dijkstra(){for (v  V) {d[v]=a[s,v]; truoc[v]=s;} d[s]=0; T= V \ {s};while (T≠) {tìm đỉnh u  T thỏa mãn d[u]=min{d[z]: z  T} T= T \ {u}; //cố định nhãn của đỉnh u6.4- Đường đi ngắn nhất20for (v  T ) //gán nhãn lại cho các đỉnh trong T if (d[v]>d[u]+a[u,v]) { d[v]=d[u]+a[u,v]; truoc[v]=u; }}} 6.4- Đường đi ngắn nhất216.4- Đường đi ngắn nhất2134651272511143226.4- Đường đi ngắn nhấtBước lặpđỉnh 1đỉnh 2đỉnh 3đỉnh 4đỉnh 5đỉnh 6khởi tạo0,11,1*∞,1∞,1∞,1∞,11--6,23,2*∞,18,22--4,4*-7,48,23----7,45,3*4----6,6*--viết d[v], truoc[v] trong mỗi ô-đỉnh có * là đang chọn để cố dịnh nhãn ở bước lặp đang xét, nhãn của nó không bị biến đổi ở các bước tiếp theo.Độ phức tạp thuật toán là O(mlogn)23Bài tậpBài 1: Viết chương trình nhập đồ thị từ bàn phím lưu trữ dạng ma trận kề.Bài 2: Viết chương trình chuyển CTDL biểu diễn đồ thị từ ma trận kề sang danh sách kề và ngược lại.Bài 3: Viết chương trình liệt kê tất cả các đỉnh của đồ thị bằng thuật toán duyệt theo chiều sâu, duyệt theo chiều rộng.Bài 4: Viết chương trình nhập đồ thị và 2 đỉnh rồi chỉ ra đường đi ngắn nhất giữa 2 đỉnh đó.24