Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 có nội dung trình bày về giải thuật tìm kiếm trong đồ thị, biểu diễn các đồ thị, biểu diễn một đồ thị vô hướng, biểu diễn một đồ thị có hướng, tìm kiếm theo chiều rộng,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8Giaûi thuaät tìm kieám trong ñoà thò Bieåu dieãn caùc ñoà thòª Hai caùch bieåu dieãn moät ñoà thò G = (V, E): – Bieåu dieãn danh saùch keà (adjacency list) ° maûng Adj goàm |V| danh saùch, 1 danh saùch cho moãi ñænh trong V. ° u  V, Adj[u] chöùa taát caû caùc ñænh v (hoaëc caùc con troû ñeán chuùng) sao cho (u, v)  E. – Nhaän xeùt ° Bieåu dieãn danh saùch keà caàn (V + E) memory. (Ñeå ñôn giaûn, kyù hieäu V vaø E thay vì |V| vaø |E|.)7.11.2004 Ch. 8: Elementary Graph Algorithms 2 Bieåu dieãn caùc ñoà thò (tieáp) – Bieåu dieãn ma traän keà (adjacency matrix) ° Ñaùnh soá ñænh 1, 2,..., |V| ° A = (aij ), ma traän |V|  |V| aij = 1 neáu (i, j)  E 0 trong caùc tröôøng hôïp coøn laïi. – Nhaän xeùt ° Bieåu dieãn ma traän keà caàn (V ) memory. 2 ° Ñoà thò thöa (sparse), |E | Bieåu dieãn moät ñoà thò voâ höôùngMoät ñoà thò voâ höôùng Bieåu dieãn Bieåu dieãn baèng moät danh saùch keà baèng moät ma traän keà7.11.2004 Ch. 8: Elementary Graph Algorithms 4 Bieåu dieãn moät ñoà thò coù höôùng Bieåu dieãn baèng Bieåu dieãn baèng moätMoät ñoà thò coù höôùng moät danh saùch keà ma traän keà7.11.2004 Ch. 8: Elementary Graph Algorithms 5 Tìm kieám theo chieàu roäng Tìm kieám theo chieàu roäng (breadth-first-search, BFS)ª Moät ñoà thò G = (V, E) – moät ñænh nguoàn s – bieåu dieãn baèng danh saùch keઠMoãi ñænh u  V – color[u]: WHITE, GREY, BLACK – p[u]: con troû chæ ñeán ñænh cha meï (predecessor hay parent) cuûa u neáu coù. – d[u]: khoaûng caùch töø s ñeán u maø giaûi thuaät tính ñöôïc.ª first-in first-out queue Q – head[Q] – thao taùc ENQUEUE(Q, v) – thao taùc DEQUEUE(Q).7.11.2004 Ch. 8: Elementary Graph Algorithms 6 Tìm kieám theo chieàu roäng (tieáp) BFS(G, s) 1 for each vertex u  V[G]  {s} 2 do color[u]  WHITE 3 d[u]   4 p[u]  NIL 5 color[s]  GRAY 6 d[s]  0 7 p[s]  NIL7.11.2004 Ch. 8: Elementary Graph Algorithms 7 Tìm kieám theo chieàu roäng (tieáp) 8 Q  {s} 9 while Q   10 do u  head[Q] 11 for each v  Adj[u] 12 do if color[v] = WHITE 13 then color[v]  GRAY 14 d[v]  d[u] + 1 15 p[v]  u 16 ENQUEUE(Q, v) 17 DEQUEUE(Q) 18 color[u]  BLACK7.11.2004 Ch. 8: Elementary Graph Algorithms 8 Thao taùc cuûa BFS leân moät ñoà thò voâ höôùng -- Ví duï r s t u  0   (a) Q s     0 v w x y r s t u 1 0   (b) Q w r  1   1 1 v w x y r s t u 1 0 2  (c) Q r t x  1 2  1 2 2 v w x y7.11.2004 Ch. 8: Elementary Graph Algorithms 9 Thao taùc cuûa BFS leân moät ñoà thò voâ höôùng -- Ví duï (tieáp) r s t u 1 0 2  (d) Q t x v 2 1 2  2 2 2 v w x y r s t u 1 0 2 3 (e) Q x v u 2 1 2  2 2 3 v w x y r s t u 1 0 2 3 (fø) Q v u y 2 1 2 3 2 3 3 v w x y7.11.2004 Ch. 8: Elementary Graph Algorithms 10 Thao taùc cuûa BFS leân moät ñoà thò voâ höôùng -- Ví duï (tieáp) r s t u 1 0 2 3 (g) Q u y 2 1 2 3 3 3 v w x y r s t u 1 0 2 3 (h) Q y 2 1 2 3 ...