Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Đồ Thị - Lê Nguyên Khôi

Nội dung text: Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Đồ Thị - Lê Nguyên Khôi

1. ế ế ậ ồ ị ườ ạ ọ ệ
2. ộ
   Đị nh ngh ĩa
   Bi ểu di ễn
   Tìm ki ếm
   Sắp xếp topo 1
3. ị 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
4. ể ễ
   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
5. ể ễ a
   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
6. ể ễ a ậ
   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
7. ể ễ
   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
8. ế
   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
9. ế
   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
10. ế ụ 1 2 3 4 5 7 8 6 9 10 11 12 13 9
11. ế ả 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
12. ế
    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
13. ế Ứ ụ
    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
14. ế
    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
15. ế ụ 1 2 3 5 4 6 7 8 9 10 11 12 13 14
16. ế ả 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
17. ế Ứ ụ
    Phân lớp cung
    Phát hi ện chu trình 16
18. ắ ế
    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
19. ắ ế ụ LTNC Toán cao cấp LTH ĐT CTDL > Trí tu ệ LTTT nhân tạo 18
20. ắ ế
    = (, ) 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 đó a b (a, c, b, d, e, f) ho ặc c d (a, b, d, c, e, f) e f 19
21. ắ ế
    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
22. ắ ế ụ DFS(a) a b DFS(c) DFS(e) L = (e) L = (e, c) DFS(d) c d DFS(f) L = (e, c, f) L = (e, c, f, d) L = (e, c, f, d, a) DFS(b) e f L = (e, c, f, d, a, b) L = (b, a, d, f, c, e) 21