Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 11: Đồ thị (Graphs) - Nguyễn Mạnh Hiển

Đồ thị (Graphs) Nguyễn Mạnh Hiển hiennm@tlu.edu.vn Nội dung • Đồ thị và biểu diễn đồ thị • Duyệt đồ thị • Sắp xếp topo • Tìm đường đi ngắn nhất Đồ thị và biểu diễn đồ thị Đồ thị • Đồ thị G = (V, E) bao gồm một tập đỉnh V và một tập cạnh E • Mỗi cạnh là một cặp (v, w) trong đó v, w  V • Đồ thị không có hướng: − Các cạnh không có thứ tự − Cạnh (v, w) giống như cạnh (w, v) • Đồ thị không có hướng được vẽ bằng các nút cho các đỉnh và các đoạn thẳng cho các cạnh v1 v2 v5 v7 v8 v3 v6 v4 Đồ thị có hướng • Trong đồ thị có hướng, E là một tập các cặp có thứ tự, nhưng không nhất thiết là tập đối xứng, tức là nếu cạnh (v, w) có mặt thì cạnh (w, v) có thể vắng mặt • Đồ thị có hướng được vẽ bằng các nút cho các đỉnh và các mũi tên cho các cạnh v1 v2 v5 v7 v8 v3 v6 v4 Đường đi và trọng số • Đường đi là một dãy đỉnh w1, w2, , wn, trong đó có một cạnh giữa hai đỉnh liên tiếp wi và wi+1 • Chiều dài của đường đi có n đỉnh bằng n – 1 (số cạnh) • Đường đi là đơn giản nếu tất cả các đỉnh trên đường đi khác nhau (ngoại trừ đỉnh đầu và đỉnh cuối có thể trùng nhau) • Các cạnh có thể có trọng số (hay chi phí) kèm theo • Chi phí của đường đi bằng tổng trọng số của các cạnh trên đường đi đó v1 v2 v5 v7 v8 v3 v6 v4 3 1 -1 5 2 -2 4 Chu trình • Chu trình là đường đi w1, w2, , wn = w1, trong đó đỉnh đầu và đỉnh cuối trùng nhau − Chu trình đơn giản nếu đường đi đó đơn giản • Trong hình vẽ bên trên: v2, v8, v6, v3, v5, v2 là một chu trình (đơn giản) trong đồ thị không có hướng, nhưng không phải như vậy trong đồ thị có hướng v1 v2 v5 v7 v8 v3 v6 v4 v1 v2 v5 v7 v8 v3 v6 v4 Đồ thị liên thông • Đồ thị không có hướng là liên thông nếu tồn tại đường đi giữa mọi cặp đỉnh trong đồ thị đó • Đồ thị có hướng thỏa mãn điều kiện trên được gọi là liên thông mạnh • Nếu một đồ thị có hướng không liên thông mạnh, nhưng đồ thị không có hướng tương ứng liên thông, thì được gọi là liên thông yếu v1 v2 v5 v7 v8 v3 v6 v4 liên thông yếu v1 v2 v5 v7 v8 v3 v6 v4 liên thông mạnh Biểu diễn đồ thị • Đánh số các đỉnh trong đồ thị từ 0 đến n-1 • Có thể dùng mảng hai chiều A có kích thước n x n (ma trận vuông cỡ n) để lưu trữ đồ thị có hướng − Với đồ thị không có trọng số, A[v][w] bằng true hoặc false tùy theo cạnh (v, w) có mặt trong đồ thị hay không − Với đồ thị có trọng số, A[v][w] bằng trọng số của cạnh (v, w) nếu cạnh đó có mặt, hoặc bằng một giá trị đặc biệt (như ) nếu cạnh đó vắng mặt • Với đồ thị không có hướng, cách biểu diễn trên (được gọi là biểu diễn ma trận kề) lưu trữ mỗi cạnh hai lần • Biểu diễn ma trận kề yêu cầu không gian O(n2) Ví dụ biểu diễn ma trận kề v1 v2 v5 v7 v0 v3 v6 v4 0 1 2 3 4 5 6 7 0 F F F F F F T F 1 F F F F T F F F 2 T F F F F F F F 3 F F F F F T T F 4 F F F F F F F F 5 F F T F F F F F 6 F F F F F F F F 7 T F F F F F F F Biểu diễn danh sách kề • Biểu diễn ma trận kề lãng phí không gian khi đồ thị thưa (có rất ít cạnh) − VD: Mỗi nút giao thông thường chỉ có 3-4 con đường giao nhau  số cạnh = O(n) • Danh sách kề là cách tiếp cận hiệu quả để lưu trữ đồ thị thưa − Đỉnh w kề với đỉnh v nếu (v, w)  E − Mỗi đỉnh giữ một danh sách các đỉnh kề với nó (các cạnh đi ra). Nếu các cạnh có trọng số thì cũng lưu trữ các trọng số vào danh sách kề này. − Yêu cầu không gian O(|V|+|E|) − Có thể dùng vector hoặc danh sách liên kết để lưu trữ danh sách đỉnh kề Ví dụ biểu diễn danh sách kề v1 v2 v5 v7 v0 v3 v6 v4 0 6, 7 1 2 2 0 3 5 4 1 5 2 6 3 7 4 Duyệt đồ thị Duyệt đồ thị • Là cách đi qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh chỉ được thăm một lần • Thăm bằng cách đánh số các đỉnh tăng dần • Sau khi duyệt, trả về tập các cạnh đã đi qua • Có hai cách duyệt: 1. Tìm kiếm theo chiều sâu 2. Tìm kiếm theo chiều rộng Tìm kiếm theo chiều sâu (depth-first search) • Với mỗi đỉnh v chưa được thăm: − Thăm v − Sau đó, thăm tiếp một đỉnh kề với v nhưng chưa được thăm • Nếu v không có đỉnh kề hoặc tất cả các đỉnh kề với nó đã được thăm, quay lui về đỉnh trước v • Duyệt đồ thị kết thúc khi tiến trình thăm và quay lui nói trên dẫn về đỉnh xuất phát s và tất cả các đỉnh kề với s khi đó đã được thăm rồi • Nếu vẫn còn đỉnh nào đó chưa được thăm, duyệt đồ thị bắt đầu lại từ đỉnh đó Thuật toán tìm kiếm theo chiều sâu depthFirstSearch() 1 với mỗi đỉnh v 2 num(v) = 0 3 edges =  4 i = 1 5 trong khi có một đỉnh v với num(v) bằng 0 6 DFS(v) 7 trả về edges DFS(v) 1 num(v) = i++ 2 với mỗi đỉnh w kề với v 3 nếu num(w) bằng 0 4 thêm cạnh (v, w) vào tập edges 5 DFS(w) Ví dụ tìm kiếm theo chiều sâu (1) Ví dụ tìm kiếm theo chiều sâu (2) Tìm kiếm theo chiều rộng (breadth-first search) • Tìm kiếm theo chiều rộng sẽ thăm tất cả các đỉnh kề với đỉnh v trước khi tiếp tục với các đỉnh khác • Trong khi đó, với tìm kiếm theo chiều sâu, ta thăm một đỉnh kề của v, sau đó thăm tiếp một đỉnh kề của đỉnh kề đó Thuật toán tìm kiếm theo chiều rộng breadthFirstSearch() 1 với mỗi đỉnh v 2 num(v) = 0 3 edges =  4 i = 1; 5 trong khi có một đỉnh v với num(v) bằng 0 6 num(v) = i++ 7 enqueue(v) 8 trong khi hàng đợi không rỗng 9 v = dequeue() 10 với mỗi đỉnh w kề với v 11 nếu num(w) bằng 0 12 num(w) = i++ 13 enqueue(w) 14 thêm cạnh (v, w) vào tập edges 15 trả về edges Ví dụ tìm kiếm theo chiều rộng (1) Ví dụ tìm kiếm theo chiều rộng (2) Sắp xếp topo Sắp xếp topo • Xét đồ thị có hướng, không chu trình • Sắp xếp topo là việc sắp xếp các đỉnh sao cho nếu có một đường đi từ vi đến vj thì vi nằm trước vj trong kết quả sắp xếp • Không thể thực hiện sắp xếp topo nếu đồ thị có một chu trình − vì với hai đỉnh v và w thuộc chu trình thì v trước w và w cũng trước v Ví dụ sắp xếp topo • Có thể có nhiều kết quả sắp xếp topo cho cùng một đồ thị • Trong đồ thị bên dưới: − Sắp topo thứ nhất: v1, v2, v5, v4, v3, v7, v6 − Sắp topo thứ hai: v1, v2, v5, v4, v7, v3, v6 Ứng dụng sắp xếp topo • Trong đồ thị yêu cầu tiên quyết của các môn học, cạnh (v, w) chỉ ra rằng môn v phải học trước môn w • Sắp xếp topo trả về một dãy môn không vi phạm điều kiện tiên quyết Thuật toán sắp xếp topo 1. Tìm một đỉnh v không có cạnh đi vào 2. Đánh số topo cho đỉnh v 3. Xóa đỉnh v và các cạnh gắn với nó 4. Áp dụng ba bước trên cho phần còn lại của đồ thị Thuật toán sắp xếp topo: Mã giả topoSort() 1 với mỗi counter = 1, 2, ..., |V| 2 tìm đỉnh v chưa được đánh số topo và có số cạnh đi vào bằng 0 3 nếu không tìm được v 4 báo lỗi đồ thị có chu trình 5 v.topoNum = counter 6 với mỗi đỉnh w kề với v 7 giảm số cạnh đi vào w một đơn vị Phân tích topoSort() • Tìm đỉnh v có số cạnh đi vào bằng 0 đòi hỏi phải quét qua tất cả các đỉnh, tức là mất thời gian O(|V|) • Phải lặp lại thao tác tìm trên |V| lần  Thời gian chạy của topoSort() là O(|V|2) Nâng cao hiệu năng thuật toán: • Sau mỗi lần xóa các cạnh gắn với đỉnh v, chỉ một số lượng nhỏ đỉnh (trong trường hợp đồ thị thưa) phải cập nhật số cạnh đi vào, tức là không cần quét của tất cả các đỉnh để tìm đỉnh v tiếp theo • Một giải pháp là lập một hàng đợi giữ các đỉnh có số cạnh đi vào bằng 0 − Mỗi khi cập nhật số cạnh đi vào của một đỉnh thì kiểm tra xem số cạnh đó có bằng 0 hay không, nếu có thì thêm đỉnh đó vào hàng đợi − Việc tìm đỉnh v chỉ đơn giản là lấy một phần tử ra khỏi hàng đợi (dequeue), tức là chỉ mất thời gian O(1) thay vì O(|V|) Tìm đường đi ngắn nhất Tìm đường đi ngắn nhất Bài toán: Cho đồ thị G = (V, E), chiều dài cạnh 𝑙𝑒  0 (e  E), nguồn s  V và đích t  V. Tìm đường đi ngắn nhất từ s đến t. nguồn s đích t chiều dài đường đi = 9 + 4 + 1 + 11 = 25 Thuật toán Dijkstra Gọi S là tập các đỉnh đã thám hiểm, trong đó ta đã biết đường đi ngắn nhất d(u) từ s đến u • Khởi tạo S = { s }, d(s) = 0 • Lặp lại: − Chọn đỉnh v chưa thám hiểm để cực tiểu hóa lượng sau đây: 𝜋 𝑣 = min 𝑒= 𝑢,𝑣 : 𝑢∈𝑆 𝑑 𝑢 + 𝑙𝑒 − Thêm v vào S, và đặt 𝑑 𝑣 = 𝜋(𝑣) Ví dụ thuật toán Dijkstra (1) Ví dụ thuật toán Dijkstra (2) Ví dụ thuật toán Dijkstra (3) Ví dụ thuật toán Dijkstra (4) Ví dụ thuật toán Dijkstra (5) Chứng minh tính đúng đắn của thuật toán Dijkstra Phát biểu: Với mỗi nút u  S, d(u) là chiều dài của đường đi ngắn nhất từ s đến u Chứng minh (bằng quy nạp theo |S|): Trường hợp cơ sở: |S| = 1  S = { s }, d(s) = 0  đúng Giả thiết quy nạp: Giả sử đúng với |S| = k  1 • Gọi v là đỉnh tiếp theo được thêm vào S, và (u, v) là cạnh mới nhất • Đường đi từ s đến v thông qua u có chiều dài (v) • Xét một đường đi P nào đó từ s đến v. Ta sẽ chứng minh 𝑙(𝑃) ≥ 𝜋(𝑣). • Gọi (x, y) là cạnh đầu tiên trong P rời khỏi S, và gọi P' là đường đi từ s đến x 𝑙 𝑃 ≥ 𝑙 𝑃′ + 𝑙 𝑥, 𝑦 ≥ 𝑑 𝑥 + 𝑙 𝑥, 𝑦 ≥ 𝜋(𝑦) ≥ 𝜋(𝑣) giả thiết quy nạp định nghĩa của 𝜋(𝑦) Dijkstra chọn v thay vì y