Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Dưới đây là bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về những cách biểu diễn của một đồ 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. | Giải thuật tìm kiếm trong đồ thị 7.11.2004 Ch. 8: Elementary Graph Algorithms Biểu diễn các đồ thị Hai cách biểu diễn một đồ thị G = (V, E): Biểu diễn danh sách kề (adjacency list) mảng Adj gồm |V| danh sách, 1 danh sách cho mỗi đỉnh trong V. u V, Adj[u] chứa tất cả các đỉnh v (hoặc các con trỏ đến chúng) sao cho (u, v) E. Nhận xét Biểu diễn danh sách kề cần (V + E) memory. (Để đơn giản, ký hiệu V và E thay vì |V| và |E|.) 7.11.2004 Ch. 8: Elementary Graph Algorithms Biểu diễn các đồ thị (tiếp) Biểu diễn ma trận kề (adjacency matrix) Đánh số đỉnh 1, 2,., |V| A = (aij ), ma trận |V| |V| aij = 1 nếu (i, j) E 0 trong các trường hợp còn lại. Nhận xét Biểu diễn ma trận kề cần (V 2) memory. Đồ thị thưa (sparse), |E | Biểu diễn một đồ thị vô hướng Biểu diễn bằng một danh sách kề Biểu diễn bằng một ma trận kề Một đồ thị vô hướng 7.11.2004 Ch. 8: Elementary Graph Algorithms Biểu diễn một đồ thị có hướng Biểu diễn bằng một danh sách kề Biểu diễn bằng một ma trận kề Một đồ thị có hướng 7.11.2004 Ch. 8: Elementary Graph Algorithms Tìm kiếm theo chiều rộng Tìm kiếm theo chiều rộng (breadth-first-search, BFS) Một đồ thị G = (V, E) một đỉnh nguồn s biểu diễn bằng danh sách kề Mỗi đỉnh u V color[u]: WHITE, GREY, BLACK p[u]: con trỏ chỉ đến đỉnh cha mẹ (predecessor hay parent) của u nếu có. d[u]: khoảng cách từ s đến u mà giải thuật tính được. first-in first-out queue Q head[Q] thao tác ENQUEUE(Q, v) thao tác DEQUEUE(Q). 7.11.2004 Ch. 8: Elementary Graph Algorithms Tìm kiếm theo chiều rộng (tiế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 7.11.2004 Ch. 8: Elementary Graph Algorithms Tìm kiếm theo chiều rộng (tiế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 . | Giải thuật tìm kiếm trong đồ thị 7.11.2004 Ch. 8: Elementary Graph Algorithms Biểu diễn các đồ thị Hai cách biểu diễn một đồ thị G = (V, E): Biểu diễn danh sách kề (adjacency list) mảng Adj gồm |V| danh sách, 1 danh sách cho mỗi đỉnh trong V. u V, Adj[u] chứa tất cả các đỉnh v (hoặc các con trỏ đến chúng) sao cho (u, v) E. Nhận xét Biểu diễn danh sách kề cần (V + E) memory. (Để đơn giản, ký hiệu V và E thay vì |V| và |E|.) 7.11.2004 Ch. 8: Elementary Graph Algorithms Biểu diễn các đồ thị (tiếp) Biểu diễn ma trận kề (adjacency matrix) Đánh số đỉnh 1, 2,., |V| A = (aij ), ma trận |V| |V| aij = 1 nếu (i, j) E 0 trong các trường hợp còn lại. Nhận xét Biểu diễn ma trận kề cần (V 2) memory. Đồ thị thưa (sparse), |E | Biểu diễn một đồ thị vô hướng Biểu diễn bằng một danh sách kề Biểu diễn bằng một ma trận kề Một đồ thị vô hướng .
