Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 12: Đồ thị - Lê Nguyên Khôi

G = (V, E) là đồ thị định hướng không chu trình Sắp xếp các đỉnh đồ thị thành một danh sách Sao cho nếu có cung (u,v) thì u cần đứng trước v trong danh sách đó Sắp xếp topo dựa trên DFS Thực hiện DFS trên đồ thị Khi kết thúc quá trình DFS trên một đỉnh u thì thêm u vào cuối danh sách Kết thúc DFS trên toàn đồ thị, đảo ngược danh sách, được sắp xếp topo

pdf22 trang | Chia sẻ: thucuc2301 | Lượt xem: 611 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 12: Đồ thị - Lê Nguyên Khôi, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Thiết Kế & Đánh Giá Thuật Toán Đồ Thị TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung  Định nghĩa  Biểu diễn  Tìm kiếm  Sắp xếp topo 1 Định Nghĩa Đồ thị  = (, ) bao gồm  Tập  các đỉnh  Tập  ⊆  ×  cạnh  Đồ thị vô hướng  Cặp cạnh không có thứ tự , = ( , )  Đồ thị định hướng  Cặp cạnh có thứ tự , ≠ , Cả hai trường hợp,  ∈ (  ) Nếu  liên thông,  ≥  − 1 ⟹ log  =  log  2 Biểu Diễn  Danh sách liền kề Mảng 1 chiều  danh sách Mỗi danh sách cho một đỉnh bao gồm Các đỉnh sao cho , ∈   Ma trận liền kề Mảng 2 chiều  ×   Đỉnh được đánh số 1, 2, ,  Giá trị 1 thể hiện có cạnh ,  ∈  3 Biểu Diễn – Danh Sách  Danh sách liền kề Mảng 1 chiều  danh sách Mỗi danh sách cho một đỉnh bao gồm Các đỉnh sao cho , ∈   1  2, 3  2!  "3#  3!  "#  4!  "3# 4 Biểu Diễn – Ma Trận  Ma trận liền kề Mảng 2 chiều  ×   Đỉnh được đánh số 1, 2, ,  Giá trị 1 thể hiện có cạnh ,  ∈  5 Biểu Diễn – So Sánh  Danh sách liền kề  Sử dụng khi đồ thị thưa   nhỏ hơn nhiều so với    Xác định danh sách đỉnh đi được từ  Ma trận liền kề  Sử dụng khi đồ thị dầy   gần bằng    Xác định có cạnh , ∈   Sử dụng cho cả đồ thị vô hướng và có hướng 6 Tìm Kiếm  Xác định cấu trúc của đồ thị  Thăm tất cả các đỉnh của  Mỗi đỉnh thăm một lần  Sử dụng các cạnh trong   02 phương pháp  Theo bề rộng (Breath First Search – BFS)  Theo bề sâu (Depth First Search – DFS) 7 Tìm Kiếm – BFS  Từ lần lượt thăm tất cả các liền kề mà chưa được thăm  Sau đó, đỉnh nào được thăm trước thì các đỉnh kề nó cũng sẽ được thăm trước  Tiếp tục cho tới khi không thể thăm đỉnh nào nữa 8 Tìm Kiếm – BFS – Ví Dụ 1 2 3 4 5 7 8 6 9 10 11 12 13 9 Tìm Kiếm – BFS – Mã Giả Algorithm BFS(u) Input: Đỉnh u chưa được thăm Khởi tạo hàng đợi Q rỗng Đánh dấu đỉnh u đã được thăm Q.enqueue(u) while Q.empty() ≠ TRUE v  Q.dequeue() for (mỗi đỉnh w kề v) if (w chưa được thăm) Đánh dấu w đã được thăm Q.enqueue(w) 10 Tìm Kiếm – BFS – Phân Tích  Thao tác trên hàng đợi: (  )  Đỉnh thêm/bớt ở hàng đợi 1 lần duy nhất  Duyệt danh sách liền kề: (  )  Khi đỉnh bị loại khỏi hàng đợi Một lần duy nhất  Độ dài danh sách    Khởi tạo: (  )  Đánh dấu các đỉnh chưa thăm  Tổng thời gian: (  +  ) 11 Tìm Kiếm – BFS – Ứng Dụng  Xác định có đường đi từ đến không  Kiểm tra tính liên thông  Xác định thành phần liên thông 12 Tìm Kiếm – DFS  Từ thăm liền kề  Từ thăm & liền kề  Cứ thể tiếp tục khi có thể được  Khi tới mà tại không thăm tiếp được, quay lại trước đó, thăm ′ khác của  Tiếp tục cho tới khi không thể thăm đỉnh nào nữa 13 Tìm Kiếm – DFS – Ví Dụ 1 2 3 5 4 6 7 8 9 10 11 12 13 14 Tìm Kiếm – DFS – Mã Giả Algorithm DFS(u) Input: Đỉnh v chưa được thăm Đánh dấu đỉnh u đã được thăm for (mỗi đỉnh v kề u) if (v chưa được thăm) Đánh dấu v đã được thăm DFS(v) 15 Tìm Kiếm – DFS – Ứng Dụng  Phân lớp cung  Phát hiện chu trình 16 Sắp Xếp Topo  Nhiều danh quan hệ trên tập đối tượng có thể biểu diễn bới đồ thị định hướng không chu trình  Quan hệ thứ tự bộ phận  Quan hệ thứ tự thời gian giữa các nhiệm vụ trong đề án  Quan hệ thứ tự thời gian giữa các môn học trong một chương trình học 17 Sắp Xếp Topo – Ví Dụ 18 CTDL > Trí tuệ nhân tạo LTHĐT LTTT LTNC Toán cao cấp Sắp Xếp Topo   = (, ) là đồ thị định hướng không chu trình  Sắp xếp các đỉnh đồ thị thành một danh sách  Sao cho nếu có cung , thì cần đứng trước trong danh sách đó 19 d a e c f b (a, c, b, d, e, f) hoặc (a, b, d, c, e, f) Sắp Xếp Topo  Sắp xếp topo dựa trên DFS  Thực hiện DFS trên đồ thị  Khi kết thúc quá trình DFS trên một đỉnh thì thêm vào cuối danh sách  Kết thúc DFS trên toàn đồ thị, đảo ngược danh sách, được sắp xếp topo 20 Sắp Xếp Topo – Ví Dụ 21 d a e c f b DFS(a) DFS(c) DFS(e) L = (e) L = (e, c) DFS(d) DFS(f) L = (e, c, f) L = (e, c, f, d) L = (e, c, f, d, a) DFS(b) L = (e, c, f, d, a, b) L = (b, a, d, f, c, e)

Các file đính kèm theo tài liệu này:

  • pdfthiet_ke_danh_gia_thuat_toanbaigiang12_dothi_4053_2032099.pdf
Tài liệu liên quan