tailieunhanh - 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! | Giaû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 . 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öôùng Moä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à 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ät Moät ñoà thò coù höôùng moät danh saùch keà ma traän keà 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 . 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 NIL 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 BLACK 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