Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Đồ thị và một vài cấu trúc phi tuyến khác - Đỗ Tuấn Anh

121 trang hapham 2260

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Đồ thị và một vài cấu trúc phi tuyến khác - Đỗ Tuấn Anh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_6_do_thi_va.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Đồ thị và một vài cấu trúc phi tuyến khác - Đỗ Tuấn Anh

Cấu trúc dữ liệu và giải thuật Đỗ Tuấn Anh anhdt@it-hut.edu.vn
Nội dung z Chương 1 – Thiết kế và phân tích (5 tiết) z Chương 2 – Giải thuật đệ quy (10 tiết) z Chương 3 – Mảng và danh sách (5 tiết) z Chương 4 – Ngăn xếp và hàng đợi (10 tiết) z Chương 5 – Cấu trúc cây (10 tiết) z Chương 8 – Tìm kiếm (5 tiết) z Chương 7 – Sắp xếp (10 tiết) z Chương 6 – Đồ thị và một vài cấu trúc phi tuyến khác (5 tiết) z Chương 9 – Sắp xếp và tìm kiếm ngoài (after)
Chương 6 – Đồ thị và một vài cấu trúc phi tuyến khác 1. Định nghĩa và khái niệm 2. Biểu diễn đồ thị • Ma trận lân cận • Danh sách lân cận 3. Phép duyệt đồ thị • Theo chiều sâu • Theo chiều rộng 4. Ứng dụng • Bài toán bao đóng truyền ứng • Bài toán sắp xếp topo 5. Giới thiệu về danh sách tổng quát, đa danh sách (not yet)
1. Định nghĩa và khái niệm
Đồ thị Một đồ thị G bao gồm một tập V(G) các đỉnh (nút)vàmột tập E(G) các cạnh (cung) là các cặp đỉnh. đỉnh a b c d cạnh e f g h i j k l V = { a, b, c, d, e, f, g, h, i, j, k, l } 12 đỉnh E = { (a, b), (a, e), (b, e), (b, f), (c, j), (c, g), (c, h), (d, h), (e, j), (g, k), (g, l), (g, h), (i, j) } 13 cạnh
Đồ thị định hướng Trong đồ thị định hướng (digraph), các cạnh là những cặp có thứ tự. TW 45 BOS NW 35 ORD SFO DL 247 DL 335 JFK AA 903 AA 1387 0 2 1 A UA 877 U MIA AA 49 AA 523 LAX DFW AA 411
Ứng dụng của đồ thị Đồ thị mô tả các mối quan hệ Mạng Internet Mạng lưới đường giao thông Nguyên tử Sơ đồ cấu trúc điều khiển Mạng lưới xã hội George Bề mặt địa lý (CAD) YokoJohnRingoPaulLinda Mạch điện
Các loại đồ thị khác Đa đồ thị cho phép có thể có nhiều cạnh giữa 2 đỉnh. a c b d f Giả đồ thị là một đa đồ thị cho phép vòng lặp (là các cạnh từ một đỉnh đến chính nó). 1 2 3 4 5 6
Cạnh và Đỉnh bậc(w) = 1 e2 w u u và v gọi là lân cận của nhau hay kề nhau (adjacent) bậc(u) = 2 e 1 v bậc vào(b) = 3 bậc ra(b) = 4 đỉnh nguồn c b a e đỉnh đích d
Đường đi Một đường đi có độ dài k là một chuỗi các đỉnh v0 , v 1 , , v k mà (vi , v i+1) với i = 0, 1, , k –1 làcạnh của G. b, c, d không phải đường đi a b c d Đường đi đơn: a, e, k, p, l, q m, h, d, c, g e f g h (không có đỉnh Không phải đường đi đơn: lặp lại) a, b, e, f, g, b, g, l j k l m n o p q
Chu trình Một chu trình là một đường đi có đỉnh đầu và đỉnh cuối trùng nhau. Một chu trình đơn không có đỉnh trùng nhau trừ đỉnh đầu và đỉnh cuối. a b c d e f g h k, j, n, k, p, o,k j k l m không phải chu trình đơn. n o p q
Đồ thị con Một đồ thị con H của G là một đồ thị; các cạnh và các đỉnh của nó là tập con của G. a b c d e f g h j k l m n o p q V(H) = {b, d, e, f, g, h, l, p, q} E(H) = {(b, e), (b, g), (e, f), (d, h), (l, p), (l, q)}
Liên thông G được gọi là liên thông nếu giữa mọi cặp đỉnh của G đều có 1 đường đi a d b c e f Nếu G là không liên thông, các đồ thị con liên thông lớn nhất được gọi là các thành phần liên thông của G. C3 C a 2 C1 d e f g b c
Cây có phải là liên thông? Có, và | E | = | V | – 1. #số cạnh #số đỉnh Nếu G là liên thông, thì | E | ≥ | V | – 1.
Đồ thị có trọng số VD.Mạng lưới giao thông 9 km B C 10 km 5 km 8 km 21 km A F D 7 km 19 km 12 km 6 km H GE 2 km
2. Biểu diễn đồ thị z 2 cách biểu diễn đồ thị phổ biến. 1. Ma trận kề (Adjacency Matrix) Sử dụng một ma trận 2 chiều 2. Danh sách kề (Adjacency List) Sử dụng một mảng của danh sách móc nối
Ma trận kề bool A [n][n]; 1 nếu(i, j) ∈ E(G) 1 A[i][j] = 0 2 0 ngược lại 0 1 2 3 4 4 3 0 01101 1 10100 2 11011 3 00101 4 10110 2 Lưu trữ: O(|V| ). Đồ thị không định hướng Thường được sử dụng với đồ thị nhỏ, không hiệu quả với đồ thị có ít cạnh
Danh sách kề Đỉnh Tập các đỉnh kề B A B 2 C 5 E 7 2 6 5 B A 2 C 6 A C C A 5 B 6 D 10 E 3 7 3 10 D C 10 E 2 E D 2 E A 7 C 3 D 2 • Danh sách kề là một mảng A[0 n-1] các danh sách, với n là số đỉnh của đồ thị. • ChNỉếsuốGclàủ địa nhmả hngướ ng,tươ tổngng ứđộngdài v ớcủi ach tấỉt csảốdanhcủa sáchđỉnh kề =| E |. • MỗNiế udanhG không sách định A[i] hướ lưng,u tr tổữngcác độ chdàiỉ làsố 2 |c Eủ |.a các đỉnh kề với đỉnhChi i. phí bộ nhớ: O(|V| + |E|). (Tốn ít bộ nhớ hơn).
Ví dụ 0 0123456789 0 0000000010 8 1 0011000101 0100100010 2 9 2 1 3 0100110000 4 0011000000 3 7 6 5 0001001000 4 5 6 0000010100 7 0100001000 8 1010000001 9 0100000010
Ví dụ 8 0 0 1 2379 8 2 148 3 2 9 145 1 4 23 5 36 3 7 57 6 6 4 5 7 16 8 029 9 18
Phân tích độ phức tạp Thao tác Danh sách kề Ma trận kề Duyệt cạnh qua v O(bậc(v)) O(|V|) Duyệt cạnh ra của v O(bậc ra(v)) O(|V|) Duyệt cạnh vào của v O(bậc vào(v)) O(|V|) Kiểm tra u kề với v O(min(bậc(u), bậc(v)) O(1) 2 Lưu trữ O(|V|+|E|) O(|V| )
Ma trận kề và danh sách kề z Danh sách kề {Tiết kiệm bộ nhớ hơn ma trận kề nếu đồ thị có ít cạnh {Thời gian kiểm tra một cạnh có tồn tại lớn hơn z Ma trận kề {Luôn luôn mấtn2 không gian bộ nhớ zĐiều này có thể làm lãng phí bộ nhớ khi đồ thị thưa {Tìm một cạnh có tồn tại hay không trong thời gian hằng số
3. Phép duyệt đồ thị z Ứng dụng {Cho một đồ thị và một đỉnh s thuộc đồ thị {Tìm tất cả đường đi từ s tới các đỉnh khác z2 thuật toán duyệt đồ thị phổ biến nhất z Tìm kiếm theo chiều rộng (BFS) • Tìm đường đi ngắn nhất trong một đồ thị không có trọng số z Tìm kiếm theo chiều sau (DFS) • Bài toán sắp xếp topo • Tìm các thành phần liên thông mạnh z Trước tiên ta sẽ xem xét BFS
Tìm kiếm theo chiều rộng Tìm đường đi ngắn nhất từ đỉnh nguồn s tới tất cả các nút. Ý tưởng:Tìm tất cả các nút tại khoảng cách 0, rồi tại khoảng cách 1, rồi đến khoảng cách 2, •Khoảng cách là số cạnh trên đường đi bắt đầu từ s 0 Ví dụ 8 Vớis là đỉnh 1 2 1 2 s 9 1 Các nút tại khoảng cách 1? 1 2, 3, 7, 9 1 Các nút tại khoảng cách 2? 3 7 8, 6, 5, 4 6 2 4 1 5 2 2 Các nút tại khoảng cách 3? 0
BFS – Giải thuật Một hàng đợi Q để lưu trữ các đỉnh đang đợi được thăm. Tại mỗi bước, một đỉnh sẽ bị xóa khỏi Q và được đánh dấu là đã thăm. Một mảng flag lưu trạng thái các đỉnh đã được thăm. Mỗi đỉnh có trạng thái “thăm” như sau: FALSE: đỉnh là chưa được thăm. TRUE: đỉnh được đưa vào hàng đợi
BSF algorithm // chưa được thăm
Ví dụ BFS b s e c g a f d Thứ tự thăm: Q: s
b s e c g a f d Thứ tự thăm: s Q: a, c
b s e c g a f d TT thăm: s, a Q: c, d Các cạnh có nét đứtchỉ ra rằng đỉnh được xét nhưng đỉnh đã được thăm. TT thăm: s, a, c Q: d, e, f
b s e c g a f d TT thăm: s, a, c, d TT thăm: s, a, c, d, e TT thăm: s, a, c, d, e, f Q: e, f Q: f, b Q: b, g
Kết thúc b s e c g a f d TT thăm: s, a, c, d, e, f, b TT thăm: s, a, c, d, e, f, b, g Q: g Q:
Cây duyệt theo chiều rộng d(b): đường đi ngắn nhất từ s đến b 3 0 b 2 s e 1 3 c g 2 1 a 2 f d BFS chỉ thăm các tập con có thể đến được từ đỉnh ban đầu
Ví dụ Danh sách kề Flag (T/F) 0 F 0 1 F 2 F 8 3 F 4 F nguồn 2 9 5 F 1 6 F 7 F 7 3 8 F 6 4 9 F 5 Khởi tạo ban đầu (tất cả = F) Q = { } Khởi tạo Q rỗng
Ví dụ Danh sách kề Flag (T/F) 0 F 0 1 F 2 T 8 3 F 4 F nguồn 2 9 5 F 1 6 F 7 F 7 3 8 F 6 4 9 F 5 2 đã được thăm Flag(2) = T. Q = { 2 } Đặt đỉnh nguồn 2 vào queue.
Ví dụ Danh sách kề Flag (T/F) 0 F 0 1 T 2 Nút kề T 8 3 F 4 T nguồn 2 9 5 F 1 6 F 7 F 7 3 8 T 6 4 9 F 5 Đánh dấu các nút kề là đã thăm. Q = {2} → { 8, 1, 4 } Lấy 2 ra khỏi queue. Đặt tất cả các nút kề chưa được thăm của 2 vào queue
Ví dụ Danh sách kề Flag (T/F) 0 T 0 1 T 2 T 8 3 F 4 T nguôn 2 9 5 F 1 6 F 7 F 7 3 Nút kề 8 T 6 4 9 T 5 Đánh dấu các nút mới được thăm. Q = { 8, 1, 4 } → { 1, 4, 0, 9 } Lấy8 ra khỏi queue. Đặt tất cả các nút kề chưa được thăm của 8 vào queue. Chú ý là 2 không được đặt vào queue nữa vì nó đã được thăm
Ví dụ Danh sách kề Flag (T/F) 0 T 1 T 0 Nút kề 2 T 8 3 T 4 T nguồn 2 9 5 F 1 6 F 7 T 7 3 8 T 6 4 9 T 5 Đánh dấu các nút mới được thăm. Q = { 1, 4, 0, 9 } → { 4, 0, 9, 3, 7 } Rút 1 ra khỏi queue. Đặt tất cả các nút kề chưa được thăm của 1 vào queue. Chỉ có nút 3 và 7 là chưa được thăm.
Ví dụ Danh sách kề Flag (T/F) 0 T 0 1 T 2 T 8 3 T 4 T nguồn Nút kề 2 9 5 F 1 6 F 7 T 7 3 8 T 6 4 9 T 5 Q = { 4, 0, 9, 3, 7 } → { 0, 9, 3, 7 } Rút 4 ra khỏi queue. 4 không có nút kề nào là chưa được thăm!
Ví dụ Danh sách kề Flag (T/F) 0 Nút kề T 0 1 T 2 T 8 3 T 4 T nguồn 2 9 5 F 1 6 F 7 T 7 3 8 T 6 4 9 T 5 Q = { 0, 9, 3, 7 } → { 9, 3, 7 } Rút 0 ra khỏi queue. 0 không có nút kề nào là chưa được thăm!
Ví dụ Danh sách kề Flag (T/F) 0 T 0 1 T 2 T 8 3 T 4 T nguồn 2 9 5 F 1 6 F 7 T 7 3 8 T 6 4 Nút kề 9 T 5 Q = { 9, 3, 7 } → { 3, 7 } Rút 9 ra khỏi queue. 9 không có nút kề nào chưa được thăm!
Ví dụ Danh sách kề Flag (T/F) 0 T 0 1 T 2 T 8 Nút kề 3 T 4 T nguồn 2 9 5 T 1 6 F 7 T 7 3 8 T 6 4 9 T 5 Đánh dấu đỉnh 5 đã được thăm. Q = { 3, 7 } → { 7, 5 } Rút 3 ra khỏi queue. Thêm nút 5 vào queue.
Ví dụ Danh sách kề Flag (T/F) 0 T 0 1 T 2 T 8 3 T 4 T nguồn 2 9 5 T 1 6 T Nút kề 7 T 7 3 8 T 6 4 9 T 5 Đánh dấu đỉnh 6 đã được thăm. Q = { 7, 5 } → { 5, 6 } Rút 7 ra khỏi queue. Thêm nút 6 vào queue.
Ví dụ Danh sách kề Flag (T/F) 0 T 0 1 T 2 T 8 3 T 4 T nguồn 2 9 Nút kề 5 T 1 6 T 7 T 7 3 8 T 6 4 9 T 5 Q = { 5, 6} → { 6 } Rút 5 ra khỏi queue. không có nút kề nào của5 là chưa được thăm.
Ví dụ Danh sách kề Flag (T/F) 0 T 0 1 T 2 T 8 3 T 4 T nguồn 2 9 5 T 1 Nút kề 6 T 7 T 3 7 6 8 T 4 9 5 T Q = { 6 } → { } Rút 6 ra khỏi queue. không có nút kề nào của6 là chưa được thăm.
Ví dụ Danh sách kề Flag (T/F) 0 T 0 1 T 2 T 8 3 T 4 T source 2 9 5 T 1 6 T 7 T 7 3 8 T 6 4 9 T 5 Kết quả? Nhìn vào Flag. Q = { } Dừng!!! Q rỗng!!! Tồn tại một đường đi từ 2 tới tất cả các đỉnh khác trong đồ thị
Độ phức tạp thời gian củaBFS (Sử dụng danh sách kề) z Giả sử đồ thị được lưu dưới dạng danh sách kề { n = số đỉnh, m = số cạnh O(n + m) Mối đỉnh vào Q duy nhất một lần. Mỗi lần lặp, thời gian tính tỉ lệ với bậc(v) + 1
Thời gian tính z Nhắc lại: Một đồ thị có m cạnh, tổng số bậc = ? Σvertex v bậc(v) = 2m z Tổng thời gian tính của vòng lặp while: O( Σvertex v (bậc(v) + 1) ) = O(n+m) được tính trên tổng của tất cả các lần lặp trong while!
Độ phức tạp thời gian củaBFS (Sử dụng ma trận kề) z Giả sử đồ thị được lưu dưới dạng ma trận kề { n = số đỉnh, m = số cạnh O(n2) Tìm các đỉnh kề củav phải duyệt toàn bộ hàng, mất thời gian O(n). Tổng trên n lần lặp, tồng thời gian tính là O(n2). Với ma trận kề,BFS làO(n2) độc lập với số cạnh m.
Cây khung theo chiều rộng z Những đường đi được tạo ra bởi phép duyệtBFS thường được vẽ như một cây (gọi là cây khung theo chiều rộng), với đỉnh bắt đầu là gốc của cây. Cây BFS với đỉnh s=2.
Tìm kiếm theo chiều sâu Depth-First Search (DFS) z DFS là một phép tìm kiếm trên đồ thị phổ biến khác {Về mặt ý tưởng, tương tự như phép duyệt theo thứ tự trước(thăm nút, rồi thăm các nút con một cách đệ quy) z DFS có thể chỉ ra một số thuộc tính của đồ thị mà BFS không thể {Nó có thể cho biết đồ thị có chu trình hay không {Học sâu hơn trong Toán Rời Rạc
Giải thuật DFS zDFS tiếp tục thăm các nút kề một cách đệ quy {Khi thămv làkề với u, tiếp tục đệ quy để thăm tất cả các nút kề chưa được thăm của v. Sau đó quay lui lạiu. u v w3 w1 w2
Ví dụ time = 1/14 a 4/5 c d e 10/11 12/13 6/7 f b g 2/9 3/8
Thứ tự thăm time = 1/14 a 4/5 c d e 10/11 12/13 6/7 a d c b g f e f b g 2/9 3/8
Cây DFS a c d e f b g
Giải thuật DFS Đánh dấu tất cả các đỉnh là chưa được thăm v đã được thăm Với các nút hàng xóm chưa được thăm, đệ quy RDFS(w) Chúng ta cũng có thể đánh dấu đường đi bằng pred[ ].
Ví dụ Danh sách kề Flag (T/F) 0 0 F - 8 1 F - 2 F - source 2 9 3 F - 1 4 F - 5 F - 3 7 6 F - 6 7 F - 4 5 8 F - 9 F - Pred Initialize visited table (all False) Initialize Pred to -1
Ví dụ Danh sách kề Flag (T/F) 0 0 F - 1 F - 8 2 T - 3 F - source 2 9 4 F - 1 5 F - 6 F - 3 7 7 6 F - 4 8 F - 5 9 F - Pred Mark 2 as visited RDFS( 2 ) Now visit RDFS(8)
Ví dụ Danh sách kề Flag (T/F) 0 0 F - 8 1 F - 2 T - source 2 9 3 F - 1 4 F - 5 F - 7 3 6 F - 6 4 7 F - 5 8 T 2 9 F - Pred Mark 8 as visited Recursive calls RDFS( 2 ) RDFS(8) mark Pred[8] 2 is already visited, so visit RDFS(0)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 F - 2 T - source 2 9 3 F - 1 4 F - 5 F - 7 3 6 F - 6 4 7 F - 5 8 T 2 9 F - Pred Mark 0 as visited Recursive calls RDFS( 2 ) RDFS(8) Mark Pred[0] RDFS(0) -> no unvisited neighbors, return to call RDFS(8)
Example Back to 8 Adjacency List Visited Table (T/F) 0 0 T 8 8 1 F - 2 T - source 2 9 3 F - 1 4 F - 5 F - 7 3 6 F - 6 4 7 F - 5 8 T 2 9 F - Pred Recursive calls RDFS( 2 ) RDFS(8) Now visit 9 -> RDFS(9)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 F - 2 T - source 2 9 3 F - 1 4 F - 5 F - 7 3 6 F - 6 4 7 F - 5 8 T 2 9 T 8 Pred Mark 9 as visited Recursive calls RDFS( 2 ) RDFS(8) Mark Pred[9] RDFS(9) -> visit 1, RDFS(1)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - source 2 9 3 F - 1 4 F - 5 F - 7 3 6 F - 6 4 7 F - 5 8 T 2 9 T 8 Pred Mark 1 as visited Recursive calls RDFS( 2 ) RDFS(8) Mark Pred[1] RDFS(9) RDFS(1) visit RDFS(3)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - source 2 9 3 T 1 1 4 F - 5 F - 7 3 6 F - 6 4 7 F - 5 8 T 2 9 T 8 Pred Mark 3 as visited Recursive calls RDFS( 2 ) RDFS(8) Mark Pred[3] RDFS(9) RDFS(1) RDFS(3) visit RDFS(4)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - source 2 9 3 T 1 1 4 T 3 5 F - 7 3 6 F - 6 4 7 F - 5 8 T 2 9 T 8 Pred RDFS( 2 ) Mark 4 as visited Recursive RDFS(8) calls RDFS(9) Mark Pred[4] RDFS(1) RDFS(3) RDFS(4) Æ STOP all of 4’s neighbors have been visited return back to call RDFS(3)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - source 2 9 3 T 1 1 4 T 3 5 F - 7 3 6 F - 6 4 7 F - 5 8 T 2 Back to 3 9 T 8 Pred RDFS( 2 ) Recursive RDFS(8) calls RDFS(9) RDFS(1) RDFS(3) visit 5 -> RDFS(5)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - source 2 9 3 T 1 1 4 T 3 5 T 3 7 3 6 F - 6 4 7 F - 5 8 T 2 9 T 8 Pred RDFS( 2 ) Recursive RDFS(8) Mark 5 as visited calls RDFS(9) RDFS(1) Mark Pred[5] RDFS(3) RDFS(5) 3 is already visited, so visit 6 -> RDFS(6)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - source 2 9 3 T 1 1 4 T 3 5 T 3 7 3 6 T 5 6 4 7 F - 5 8 T 2 9 T 8 Pred RDFS( 2 ) RDFS(8) Recursive RDFS(9) Mark 6 as visited calls RDFS(1) Mark Pred[6] RDFS(3) RDFS(5) RDFS(6) visit 7 -> RDFS(7)
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - source 2 9 3 T 1 1 4 T 3 5 T 3 7 3 6 T 5 6 4 7 T 6 5 8 T 2 9 T 8 Pred RDFS( 2 ) RDFS(8) Recursive RDFS(9) Mark 7 as visited calls RDFS(1) Mark Pred[7] RDFS(3) RDFS(5) RDFS(6) RDFS(7) -> Stop no more unvisited neighbors
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - 3 T 1 source 2 9 4 T 3 1 5 T 3 3 7 6 T 5 6 7 T 6 4 5 8 T 2 9 T 8 Pred RDFS( 2 ) RDFS(8) Recursive RDFS(9) calls RDFS(1) RDFS(3) RDFS(5) RDFS(6) -> Stop
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - 3 T 1 source 2 9 4 T 3 1 5 T 3 3 7 6 T 5 6 7 T 6 4 5 8 T 2 9 T 8 Pred RDFS( 2 ) RDFS(8) Recursive RDFS(9) calls RDFS(1) RDFS(3) RDFS(5) -> Stop
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - 3 T 1 source 2 9 4 T 3 1 5 T 3 3 7 6 T 5 6 7 T 6 4 5 8 T 2 9 T 8 Pred RDFS( 2 ) RDFS(8) Recursive RDFS(9) calls RDFS(1) RDFS(3) -> Stop
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - 3 T 1 source 2 9 4 T 3 1 5 T 3 3 7 6 T 5 6 7 T 6 4 5 8 T 2 9 T 8 Pred RDFS( 2 ) RDFS(8) Recursive RDFS(9) calls RDFS(1) -> Stop
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - 3 T 1 source 2 9 4 T 3 1 5 T 3 3 7 6 T 5 6 7 T 6 4 5 8 T 2 9 T 8 Pred RDFS( 2 ) RDFS(8) Recursive RDFS(9) -> Stop calls
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - 3 T 1 source 2 9 4 T 3 1 5 T 3 3 7 6 T 5 6 7 T 6 4 5 8 T 2 9 T 8 Pred RDFS( 2 ) RDFS(8) -> Stop Recursive calls
Example Adjacency List Visited Table (T/F) 0 0 T 8 8 1 T 9 2 T - 3 T 1 source 2 9 4 T 3 1 5 T 3 3 7 6 T 5 6 7 T 6 4 5 8 T 2 9 T 8 Pred RDFS( 2 ) -> Stop Recursive calls
Example 0 Adjacency List Visited Table (T/F) 8 0 T 8 1 T 9 source 2 9 2 T - 1 3 T 1 4 T 3 3 7 5 T 3 6 6 T 5 4 5 7 T 6 8 T 2 9 T 8 Pred Check our paths, does DFS find valid paths? Yes. Try some examples. Path(0) -> Path(6) -> Path(7) ->
Độ phứctạpthờigiancủaDFS (Sử dụng danh sách kề) z Không bao giờ thămmột nút quá 1 lần z Thựchiệnkiểmtratấtcả cạnh củamột đỉnh {Σv bậc(v) = 2m vớim làtổng số cạnh z Do vậythời gian tính củaDFS tỉ lệ thuậnvớisố cạnh và sốđỉnh (giống BFS) {O(n + m) z Hoặcviết: {O(|v|+|e|) |v| = tổng sốđỉnh (n) |e| = tổng số cạnh (m)
Depth-First Search a h i c d e j f k l b g DFS đảmbảothămmọi đỉnh liên thông với đỉnh ban đầu. Chophépxácđịnh đồ thị có liên thông không, và tìm các thành phầnliên thông của đồ thị.
Ứng dụng của đồ thị zBài toán bao đóng truyền ứng (transitive closure) zBài toán sắpxếp topo (topological sort)
Bài toán bao đóng truyền ứng zĐặtvấn đề: Cho đồ thị G {Có đường đitừ A đến B không?
Bao đóng truyền ứng là gì? zBao đóng truyền ứng của một đồ thị định hướng có cùng số nút với đồ thị ban đầu. zNếu có một đường đi định hướng từ nút a tới b, thì bao đóng truyền ứng sẽ chứa một Đồ thị Bao đóng truyền ứng taới b, thìb bao đóng truyền ứang sẽ chbứamột d c d c A graph Transitive closure
Biểudiễn đồ thị dướidạng ma trậnkề Kích thướccủama trận 2 0 1 1 0 1 0 0 0 1 1 1 3 A = 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 5 4
Bao đóng truyền ứng của G(V,E) là 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1
Bao đóng truyền ứng và phép nhân ma trận Xét Phép toán logic, AND, OR
Bao đóng truyền ứng và phép nhân ma trận Xét ?
Bao đóng truyền ứng và phép nhân ma trận Xét ?
Bao đóng truyền ứng và phép nhân ma trận Xét ?
Giảithuật Warshall Algorithm Warshall (A, P, n) Input: A là ma trậnkề biểudiễn đồ thị, n là số đỉnh của đồ thị Output: P là bao đóng truyền ứng của đồ thị 1. P = A; 2. for k = 1 to n do 3. for i = 1 to n do 4. for j = 1 to n do 5. P[i][j] = P[i][j] | P[i][k] & P[k][j];
Độ phứctạpcủa phép nhân 2 ma trận kích thước nxn? Thựchiện bao nhiêu phép nhân ma trận kích thước nxn? Độ phứctạp
Bài toán sắpxếp topo
Ví dụ: Cấutrúcmônhọc NMTH CTDL TRR KTMT 342 221 KTLT 211 251 271 GT TCC 252 231 303 343 TTKH 361 381 327 341 334 336 362 332
Đồ thịđịnh hướng, không có chu trình z Một đồ thịđịnh hướng là mộtchuỗicácđỉnh (v0, v1, . . . , vk) {(vi, vi+1) đượcgọilàmột cung (k gọilàcạnh) z Một chu trình định hướng là một đường đi định hướng với đỉnh đầu trùng với đỉnh cuối. z Một đồ thịđịnh hướng không có chu trình nếu nó không chứabấtkỳ chu trình định hướng nào
Ứng dụng của đồ thịđịnh hướng z Đồ thịđịnh hướng thường đượcsử dụng để thể hiệncác công việccóthứ tự phụ thuộc z Có nghĩalàcôngviệc này chỉ bắt đầu khi công việckia kết thúc z Các quan hệ thứ tự ràng buộc đó đượcthể hiệnbằng các cung z Một cung (i,j) có nghĩalàcông việcjkhông thể bắt đầu cho đếnkhicông việcikết thúc i j z Rõ ràng, để các ràng buộc không bị lặpvôhạn thì đồ thị phải là không có chu trình.
Bậcvàovàbậcra z Vì các cạnh là có định hướng zPhải xem xét các cung là “đi vào” hay “đi ra” {Khái niệm zBậc vào(v) zBậcra(v)
Bậcra zTổng số cung đi “ra” khỏi v zTổng số bậc ra? (m=#số cạnh) ∑ bac_ra(v) = m vertex v
Bậcvào zTổng số cung đi “vào” v zTổng số bậcvào? ∑ bac_vao(v) = m vertex v
Ví dụ Bậc_vào(2)? 6 3 8 Bậc_vào(8)? Bậc_ra(0)? 0 7 2 9 1 5 4
Sắpxếptopo z Sắpxếp topo là thuật toán cho đồ thịđịnh hướng không có chu trình z Nó có thểđược xem như việc định ra mộtthứ tự tuyếntínhchocácđỉnh, với các quan hệ thứ tự thể hiệnbởi các cung 6 3 Ví dụ: 8 0, 1, 2, 5, 9 0, 4, 5, 9 0 2 7 9 1 0, 6, 3, 7 ? 5 4
Sắpxếptopo z Ý tưởng: { Bắt đầuvới đỉnh có bậc vào = 0! { Nếu không tồntại, đồ thị là có chu trình 1. Tìm đỉnh i có bậc vào = 0. Ghi vào dãy thứ tự tuyếntính 2. Xóa đỉnh i và các cung đirakhỏi đỉnh i khỏi đồ thị 3. Đồ thị mớivẫnlàđịnh hướng không có chu trình. Do đó, lặplạibước1-2 chođếnkhi không còn đỉnh nào trong đồ thị.
Giảithuật Tìm tấtcảđỉnh bắt đầu Giảmbậc vào(w) Thêm các đỉnh bắt đầu mớivàoQ
Ví dụ Bậcvào 0 614 0 0 1 2 1 1 start 6 3 2 75 2 2 8 3 8 3 1 4 5 4 1 0 7 2 9 9 1 5 5 2 6 32 6 1 5 7 8 7 1 4 8 9 8 2 9 9 2 Q = { 0 } OUTPUT: 0
Ví dụ Bậcvào 0 614 0 0 1 2 1 1 -1 6 3 2 75 2 2 8 3 8 3 1 4 5 4 1 -1 0 7 2 9 9 1 5 5 2 6 32 6 1 -1 5 7 8 7 1 4 8 9 8 2 9 9 2 Dequeue 0 Q = { } -> remove 0’s arcs – adjust Decrement 0’s indegrees of neighbors neighbors OUTPUT:
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 6 3 2 75 2 2 8 3 8 3 1 4 5 4 0 0 7 2 9 9 1 5 5 2 6 32 6 0 5 7 8 7 1 4 8 9 8 2 9 9 2 Dequeue 0 Q = { 6, 1, 4 } Enqueue all starting points Enqueue all new start points OUTPUT: 0
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 6 3 2 75 2 2 -1 8 3 8 3 1 -1 4 5 4 0 7 2 9 9 1 5 5 2 6 32 6 0 5 7 8 7 1 4 8 9 8 2 9 9 2 Dequeue 6 Q = { 1, 4 } Remove arcs Adjust indegrees Adjust neighbors of neighbors indegree OUTPUT: 0 6
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 3 2 75 2 1 8 3 8 3 0 4 5 4 0 7 2 9 9 1 5 5 2 6 32 6 0 5 7 8 7 1 4 8 9 8 2 9 9 2 Dequeue 6 Q = { 1, 4, 3 } Enqueue 3 Enqueue new start OUTPUT: 0 6
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 3 2 75 2 1 -1 8 3 8 3 0 4 5 4 0 7 2 9 9 1 5 5 2 6 32 6 0 5 7 8 7 1 4 8 9 8 2 9 9 2 Dequeue 1 Q = { 4, 3 } Adjust indegrees of neighbors Adjust neighbors of 1 OUTPUT: 0 6 1
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 3 2 75 2 0 8 3 8 3 0 4 5 4 0 7 2 9 5 9 5 2 6 32 6 0 5 7 8 7 1 4 8 9 8 2 9 9 2 Dequeue 1 Q = { 4, 3, 2 } Enqueue 2 Enqueue new starting points OUTPUT: 0 6 1
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 3 2 75 2 0 8 3 8 3 0 4 5 4 0 7 2 9 5 9 5 2 -1 6 32 6 0 5 7 8 7 1 4 8 9 8 2 9 9 2 Dequeue 4 Q = { 3, 2 } Adjust indegrees of neighbors Adjust 4’s neighbors OUTPUT: 0 6 1 4
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 3 2 75 2 0 8 3 8 3 0 4 5 4 0 7 2 9 5 9 5 1 6 32 6 0 5 7 8 7 1 8 9 8 2 9 9 2 Dequeue 4 Q = { 3, 2 } No new start points found NO new start points OUTPUT: 0 6 1 4
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 3 2 75 2 0 8 3 8 3 0 4 5 4 0 7 2 9 5 9 5 1 6 32 6 0 5 7 8 7 1 8 9 8 2 -1 9 9 2 Dequeue 3 Q = { 2 } Adjust 3’s neighbors OUTPUT: 0 6 1 4 3
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 8 3 8 3 0 4 5 4 0 7 2 9 5 9 5 1 6 32 6 0 5 7 8 7 1 8 9 8 1 9 9 2 Dequeue 3 Q = { 2 } No new start points found OUTPUT: 0 6 1 4 3
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 8 3 8 3 0 4 5 4 0 7 2 9 5 9 5 1 -1 6 32 6 0 5 7 8 7 1 -1 8 9 8 1 9 9 2 Dequeue 2 Q = { } Adjust 2’s neighbors OUTPUT: 0 6 1 4 3 2
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 8 3 8 3 0 4 5 4 0 7 9 5 9 5 0 6 32 6 0 5 7 8 7 0 8 9 8 1 9 9 2 Dequeue 2 Q = { 5, 7 } Enqueue 5, 7 OUTPUT: 0 6 1 4 3 2
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 8 3 8 3 0 4 5 4 0 7 9 5 9 5 0 6 32 6 0 5 7 8 7 0 8 9 8 1 9 9 2 -1 Dequeue 5 Q = { 7 } Adjust neighbors OUTPUT: 0 6 1 4 3 2 5
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 8 3 8 3 0 4 5 4 0 7 9 5 9 5 0 6 32 6 0 7 8 7 0 8 9 8 1 9 9 1 Dequeue 5 Q = { 7 } No new starts OUTPUT: 0 6 1 4 3 2 5
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 8 3 8 3 0 4 5 4 0 7 9 5 9 5 0 6 32 6 0 7 8 7 0 8 9 8 1 -1 9 9 1 Dequeue 7 Q = { } Adjust neighbors OUTPUT: 0 6 1 4 3 2 5 7
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 8 3 8 3 0 4 5 4 0 9 5 9 5 0 6 32 6 0 7 8 7 0 8 9 8 0 9 9 1 Dequeue 7 Q = { 8 } Enqueue 8 OUTPUT: 0 6 1 4 3 2 5 7
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 8 3 8 3 0 4 5 4 0 9 5 9 5 0 6 32 6 0 7 8 7 0 8 9 8 0 9 9 1 -1 Dequeue 8 Q = { } Adjust indegrees of neighbors OUTPUT: 0 6 1 4 3 2 5 7 8
Ví dụ Bậcvào 0 614 0 0 1 2 1 0 2 75 2 0 3 8 3 0 4 5 4 0 9 5 9 5 0 6 32 6 0 7 8 7 0 8 9 8 0 Dequeue 8 Q = { 9 } 9 9 0 Enqueue 9 Dequeue 9 Q = { } STOP – no neighbors OUTPUT: 0 6 1 4 3 2 5 7 8 9
Ví dụ 6 3 8 0 2 7 9 1 5 4 OUTPUT: 0 6 1 4 3 2 5 7 8 9
Sắpxếp topo: Độ phứctạp zKhông bao giờ thăm1 đỉnh nhiềuhơn1 lần zVớimỗi đỉnh, phảixéttấtcả các cung ra {Σ bậc_ra(v) = m zĐộ phứctạpvề thời gian: O(n + m)