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

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)