intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Thuật toán ứng dụng: Đồ thị nâng cao

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:100

Thêm vào BST
Báo xấu
12
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Thuật toán ứng dụng: Đồ thị nâng cao" trình bày các nội dung chính sau đây: Đồ thị có trọng số; Cấu trúc dữ liệu các tập không giao nhau – UNION-FIND; Cây khung nhỏ nhất - MST; Đường đi ngắn nhất; Một số bài toán kinh điển trên đồ thị; Một số đồ thị đặc biệt. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Thuật toán ứng dụng: Đồ thị nâng cao

  1. Đồ Thị Nâng Cao THUẬT TOÁN ỨNG DỤNG
  2. 1 Đồ thị có trọng số 2 Cấu trúc dữ liệu các tập không giao nhau – UNION-FIND 3 Cây khung nhỏ nhất - MST 4 Đường đi ngắn nhất 5 Một số bài toán kinh điển trên đồ thị 6 Một số đồ thị đặc biệt 3 / 59
  3. 1 Đồ thị có trọng số 2 Cấu trúc dữ liệu các tập không giao nhau – UNION-FIND 3 Cây khung nhỏ nhất - MST 4 Đường đi ngắn nhất 5 Một số bài toán kinh điển trên đồ thị 6 Một số đồ thị đặc biệt 4 / 59
  4. Đồ thị có trọng số Trong phần này ta xét đồ thị mà mỗi cạnh của nó có trọng số đi kèm giá trị trên cạnh trọng số trên cạnh ví dụ: khoảng cách của con đường, chi phí truyền thông giữa hai nút mạng, . . . Biểu diễn đồ thị có trọng số bởi danh sách kề mở rộng 5 / 59
  5. Đồ thị có trọng số struct edge { int u , v ; 1 int weight ; 9 -7 edge ( int _u , int _v , int _w ) { 0 u = _u ; 2 3 v = _v ; weight = _w ; 5.1 } }; 4 6 / 59
  6. Đồ thị có trọng số vector < edge > Adj [5]; 1 Adj [1]. push_back ( edge (1 , 2 , 9)); Adj [1]. push_back ( edge (1 , 3 , -7)); 9 -7 0 Adj [2]. push_back ( edge (2 , 1 , 9)); 2 3 Adj [2]. push_back ( edge (2 , 3 , 0)); 5.1 Adj [3]. push_back ( edge (3 , 1 , -7)); Adj [3]. push_back ( edge (3 , 2 , 0)); 4 Adj [3]. push_back ( edge (3 , 4 , 5.1)); Adj [4]. push_back ( edge (4 , 3 , 5.1)); 7 / 59
  7. 1 Đồ thị có trọng số 2 Cấu trúc dữ liệu các tập không giao nhau – UNION-FIND 3 Cây khung nhỏ nhất - MST 4 Đường đi ngắn nhất 5 Một số bài toán kinh điển trên đồ thị 6 Một số đồ thị đặc biệt 8 / 59
  8. Union-Find Cho n phần tử Cần quản lý vào các tập không giao nhau Mỗi phần tử ở trong đúng 1 tập Items = {1, 2, 3, 4, 5, 6} Collections = {1, 4}, {3, 5, 6}, {2} Collections = {1}, {2}, {3}, {4}, {5}, {6} Hai toán tử hiệu quả: Find(x) và Union(x,y). 9 / 59
  9. Union-Find Items = {1, 2, 3, 4, 5, 6} Collections = {1, 4}, {3, 5, 6}, {2} Find(x) trả về phần tử đại diện của tập chứa x Find(1) = 1 Find(4) = 1 Find(3) = 5 Find(5) = 5 Find(6) = 5 Find(2) = 2 a và b thuộc cùng một tập khi và chỉ khi Find(a) == Find(b) 10 / 59
  10. Union-Find Items = {1, 2, 3, 4, 5, 6} Collections = {1, 4}, {3, 5, 6}, {2} Union(x, y) trộn tập chứa x và tập chứa y vào nhau union(4, 2) Collections = {1, 2, 4}, {3, 5, 6} union(3, 6) Collections = {1, 2, 4}, {3, 5, 6} union(2, 6) Collections = {1, 2, 3, 4, 5, 6} 11 / 59
  11. Cài đặt Union-Find Hợp nhất nhanh với kỹ thuật nén đường (Quick Union with path compression) Cực kỳ dễ cài đặt Cực kỳ hiệu quả 1 struct Union_Find { 2 vector < int > iParent ; 3 Union_Find ( int n ) { 4 iParent = vector < int >( n ); 5 for ( int i = 0; i < n ; ++ i ) { 6 iParent [ i ] = i ; 7 } 8 } 9 // toan tu Find va Union 10 }; 12 / 59
  12. Cài đặt Union-Find 1 // toan tu Find va Union 2 3 int Find ( int x ) { 4 if ( iParent [ x ] == x ) { 5 return x ; 6 } else { 7 iParent [ x ] = Find ( iParent [ x ]); // Nen parent 8 return iParent [ x ]; 9 } 10 } 11 12 void Unite ( int x , int y ) { 13 iParent [ Find ( x )] = Find ( y ); 14 } 13 / 59
  13. Ứng dụng của Union-Find Union-Find quản lý các tập không giao nhau Xử lý từng loại các tập không giao nhau tùy thời điểm Các bài toán ứng dụng quen thuộc thường trên đồ thị 14 / 59
  14. Union-Find trên đồ thị 1 7 2 4 5 3 6 15 / 59
  15. Union-Find trên đồ thị 1 7 2 4 5 3 6 items = {1, 2, 3, 4, 5, 6, 7} 15 / 59
  16. Union-Find trên đồ thị 1 7 2 4 5 3 6 items = {1, 2, 3, 4, 5, 6, 7} collections = {1, 4, 7}, {2}, {3, 5, 6} 15 / 59
  17. Union-Find trên đồ thị 1 7 2 4 5 3 6 items = {1, 2, 3, 4, 5, 6, 7} collections = {1, 4, 7}, {2}, {3, 5, 6} union(2, 5) 15 / 59
  18. Union-find trên đồ thị 1 7 2 4 5 3 6 Items = {1, 2, 3, 4, 5, 6, 7} Collections = {1, 4, 7}, {2, 3, 5, 6} 16 / 59
  19. Union-find trên đồ thị 1 7 2 4 5 3 6 Items = {1, 2, 3, 4, 5, 6, 7} Collections = {1, 4, 7}, {2, 3, 5, 6} Union(6, 2) 16 / 59
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
6=>0