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

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

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

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

Sau khi học xong chương 5 Đồ thị nằm trong bài giảng cấu trúc dữ liệu và giải thuật sinh viên có kiến thức về: những kiến thức căn bản về lý thuyết đồ thị, cách biểu diễn, một số thuật toán trên đồ thị, đánh giá thuật toán và một số ứng dụng của đồ thị.

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 Cấu trúc dữ liệu và giải thuật: Chương 5 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

  1. Chương 5: Đồ thị Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM
  2. Mục tiêu  Trình bày những kiến thức căn bản về lý thuyết đồ thị, cách biểu diễn, một số thuật toán trên đồ thị  Đánh giá thuật toán  Một số ứng dụng của đồ thị Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 2
  3. Định nghĩa Anchorage Boston Minneapolis Seattle Hartford SF Austin Atlanta Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 3
  4. Định nghĩa  Đồ thị G = (V,E) V= tập hợp hữu hạn các phần tử (đỉnh hay nút) E  V × V, tập hữu hạn các cạnh (cung) a b Đỉnh c Cung d e Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 4
  5. Các khái niệm  Nếu (x,y)  E  x gọi là đỉnh gốc, y là ngọn  Nếu x ≡ y, (x,y) gọi là khuyên  Một dãy u1, u2, …, un, ui  V (i=1,n) gọi là một đường, nếu (ui-1,ui)  E  Độ dài đường: length(u1,u2,…,un)=n  (u1,u2,…,un) đường đi đơn, nếu ui≠uj, 1
  6. Các khái niệm  Chu trình (cycle) = (u1,u2,…,un), u1≡ un  Đồ thị định hướng (directed graph)  (x,y)  E : (x,y) ≠ (y,x)  Đồ thị vô hướng  (x,y)  E : (y,x)  E  (x,y) ≡ (y,x) Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 6
  7. Các khái niệm  CBDC là một chu trình B B C A C A Đường đi đơn D D Chu trình Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 7
  8. Các khái niệm Đồ thị vô hướng Đồ thị định hướng Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 8
  9. Các khái niệm  Tính liên thông (connectivity)  Trong đồ thị G, hai đỉnh x,y gọi là liên thông (connected), nếu có một đường từ x đến y  Đồ thị G liên thông, nếu (x,y)  E,  đường đi từ x đến y  Đồ thị G gọi là có trọng số, nếu mỗi cung được gán một giá trị số đặc trưng Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 9
  10. Các khái niệm Đồ thị liên thông Đồ thị không liên thông Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 10
  11. Các khái niệm  Đồ thị có trọng số 0 10 20 1 1 2 4 5 3 Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 11
  12. Biểu diễn đồ thị  Biểu diễn bằng ma trận kề  Adjacency matrice  Biểu diễn bằng danh sách kề  Adjacency list Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 12
  13. Biểu diễn đồ thị bằng ma trận kề  Xét G=(V,E) với V={x1,…,xn}  Biểu diễn G bằng ma trận A = (aij), i,j = 1..n  aij = 1, nếu Ǝ (xi,xj)  E  aij = 0, nếu !Ǝ (xi,xj)  E Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 13
  14. Biểu diễn đồ thị bằng ma trận kề A[i][j] 0 1 2 3 0 0 0 1 1 0 1 1 0 1 1 1 2 1 1 0 1 2 3 0 1 1 0 3 0 1 1 0 1 0 1 1 A= 1 1 0 1 0 1 1 0 Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 14
  15. Biểu diễn đồ thị bằng ma trận kề A[i][j] 0 1 2 3 0 0 1 1 1 0 1 0 0 0 1 2 0 0 0 1 1 2 3 0 0 0 0 3 0 1 1 1 0 0 0 1 A= 0 0 0 1 0 0 0 0 Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 15
  16. Biểu diễn đồ thị bằng ma trận kề x2 0 1 1 0 0 x1 x3 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 x5 x4 1 0 0 1 0 Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 16
  17. Biểu diễn đồ thị bằng ma trận kề x2 0 1 1 0 0 x1 x3 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 x5 x4 1 0 0 1 1 Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 17
  18. Biểu diễn đồ thị bằng ma trận kề A[i][j] 0 1 2 3 0 0 20 10 1 1 20 0 0 5 0 2 10 0 0 4 20 10 3 1 5 4 0 1 1 2 5 0 20 10 1 4 20 0 0 5 3 A= 10 0 0 4 1 5 4 0 Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 18
  19. Biểu diễn đồ thị bằng ma trận kề  Chú ý  Đối với đồ thị không định hướng, ma trận kề là ma trận đối xứng  Đối với đồ thị định hướng, số lượng phần tử 0 khá lớn  Đối với đồ thị có trọng số, thay thế giá trị 1 bằng giá trị trọng số Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 19
  20. Biểu diễn đồ thị bằng danh sách kề  Là một mảng các danh sách  Ở đây, n hàng của ma trận kề thay thế bằng n danh sách liên kết động  Mỗi đỉnh của G có một danh sách, mỗi nút trong danh sách thể hiện các đỉnh lân cận của nút này  Cấu trúc mỗi nút  id: tên đỉnh (chỉ số, danh hiệu)  next: con trỏ đến nút kế tiếp Khoa Công Nghệ Thông Tin - Trường Đại học Ngân hàng TP.HCM 20
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
28=>1