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 - Trường ĐH Văn Lang

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

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

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 Lý thuyết đồ thị, cung cấp cho người học những kiến thức như: giới thiệu đồ thị; biểu diễn đồ thị; thuật toán duyệt đồ thị; bài toán tìm đường ngắn nhấ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 Cấu trúc dữ liệu và giải thuật: Chương 5 - Trường ĐH Văn Lang

  1. GIỚI THIỆU • Đồ thị là một cấu trúc dữ liệu trừu tượng dựa trên các khái niệm toán học về đồ thị. • Đồ thị được xem là tổng quát hóa của cấu trúc cây. Tuy nhiên, đồ thị có mối quan hệ phức tạp hơn là quan hệ cha-con trong cấu trúc cây. • Đồ thị được sử dụng trong nhiều ứng dụng như cây gia phả, mạng quản lý chuyến bay v.v… 3 KHOA CÔNG NGHỆ THÔNG TIN
  2. GIỚI THIỆU • Một đồ thị G là một tập hợp không có thứ tự (V, E), trong đó V : là các đỉnh của đồ thị E : là các cạnh (cung) biểu diễn mối quan hệ giữa các đỉnh A B C V(G) = {A, B, C, D, E} E(G) = {(A, B), (A, D), (B, C}, (B, D), D E (C, E), (D, E)} 4 KHOA CÔNG NGHỆ THÔNG TIN
  3. GIỚI THIỆU • Một đồ thị G có thể có hướng hoặc vô hướng. • Nếu đồ thị có hướng thì cạnh nối hai đỉnh có mũi tên đại diện cho hướng nối. Đồ thị vô hướng Đồ thị có hướng A B C A B C D E D E 5 KHOA CÔNG NGHỆ THÔNG TIN
  4. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. SỬ DỤNG MA TRẬN KỀ • Hai đỉnh kề nhau nếu có cạnh nối giữa chúng • Ta dùng một ma trận với dòng, cột biểu diễn cho các đỉnh của đồ thị. • Biểu diễn cạnh trên ma trận kề 1 Nếu đỉnh i kề đỉnh j 𝑎𝑖𝑗 = 0 Ngược lại 6 KHOA CÔNG NGHỆ THÔNG TIN
  5. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. SỬ DỤNG MA TRẬN KỀ A B C A B C D E D E A B C D E A B C D E A 0 1 0 1 0 A 0 1 0 1 0 B 1 0 1 1 0 B 0 0 0 1 0 C 0 1 0 0 1 C 0 1 0 0 0 D 1 1 0 0 1 D 0 0 0 0 1 E 0 0 1 1 0 E 0 0 1 0 0 7 KHOA CÔNG NGHỆ THÔNG TIN
  6. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. SỬ DỤNG MA TRẬN KỀ 4 5 A B C Đồ thị có trọng số là đồ thị mà có gán dữ liệu trên mỗi 2 7 cạnh. 1 D E 3 Biểu diễn đồ thị có trọng số A B C D E A 0 4 0 2 0 B 0 0 0 7 0 C 0 5 0 0 0 D 0 0 0 0 3 E 0 0 1 0 0 8 KHOA CÔNG NGHỆ THÔNG TIN
  7. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 1. SỬ DỤNG MA TRẬN KỀ 4 5 • Đối với đồ thị đơn (không có vòng), A B C ma trận kề có đường chéo chính 2 mang giá trị 0 7 1 • Ma trận kề đồ thị vô hướng thì đối D 3 E xứng A B C D E • Bộ nhớ của ma trận kề là O(n2), n là A 0 4 0 2 0 số đỉnh của đồ thị. B 0 0 0 7 0 C 0 5 0 0 0 D 0 0 0 0 3 E 0 0 1 0 0 9 KHOA CÔNG NGHỆ THÔNG TIN
  8. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 2. SỬ DỤNG DANH SÁCH KỀ • Danh sách kề gồm các đỉnh của đồ thị V(G). • Mỗi đỉnh vi là một danh sách liên kết lưu trữ những đỉnh vj , vj+1, … nối tới vi • Thường dùng để lưu đồ thị nhỏ và vừa. • Biểu diễn đồ thị thưa (có ít cạnh nối) trong bộ nhớ máy tính. 10 KHOA CÔNG NGHỆ THÔNG TIN
  9. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 2. SỬ DỤNG DANH SÁCH KỀ • Danh sách kề biểu diễn đồ thị vô hướng. A B D NULL A B C B A C NULL C B E NULL D E D A B NULL E C D NULL 11 KHOA CÔNG NGHỆ THÔNG TIN
  10. THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG • Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng. A B C Xuất phát từ đỉnh A D E 12 KHOA CÔNG NGHỆ THÔNG TIN
  11. THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG • Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng. A B B1: Xuất phát từ đỉnh A B2: Đi qua đỉnh B, D D 13 KHOA CÔNG NGHỆ THÔNG TIN
  12. THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG • Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng. A B C B1: Xuất phát từ đỉnh A B2: Đi qua đỉnh B, D B3: Xuất phát từ đỉnh B D B4: Đi qua đỉnh C 14 KHOA CÔNG NGHỆ THÔNG TIN
  13. THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG • Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng. A B C B1: Xuất phát từ đỉnh A B2: Đi qua đỉnh B, D B3: Xuất phát từ đỉnh B D B4: Đi qua đỉnh C B5: Xuất phát từ đỉnh D 15 KHOA CÔNG NGHỆ THÔNG TIN
  14. THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG • Duyệt theo chiều rộng (Breadth-First Search) đồ thị vô hướng. A B C B1: Xuất phát từ đỉnh A B2: Đi qua đỉnh B, D B3: Xuất phát từ đỉnh B D E B4: Đi qua đỉnh C B5: Xuất phát từ đỉnh D B6: Đi qua đỉnh E Dừng thuật toán 16 KHOA CÔNG NGHỆ THÔNG TIN
  15. THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG GIẢI THUẬT : Duyệt theo chiều rộng (BFS) procedure BFS(G: đồ thị với các đỉnh v1, v2, …, vn) T := cây chỉ chứa một đỉnh ban đầu v1 L := danh sách rỗng dùng để chứa các đỉnh đã đi qua Đặt đỉnh v1 vào danh sách L while L không rỗng remove đỉnh v1 từ L for mỗi đỉnh kề w với đỉnh v1 do if w không có trong L and không có trong T then add w vào L add w and cạnh {v1, w} vào T 17 KHOA CÔNG NGHỆ THÔNG TIN
  16. THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG Độ phức tạp không gian • Tất cả các đỉnh tại mức đang xét sẽ được lưu cho đến khi các đỉnh kề được đi qua. • Độ phức tạp không gian tỉ lệ thuận với số đỉnh ở mức sâu nhất của đồ thị. • Cho đồ thị có b là số đỉnh kề của mỗi đỉnh và chiều sâu d. Độ phức tạp không gian là số đỉnh ở mức sâu nhất O(bd). 18 KHOA CÔNG NGHỆ THÔNG TIN
  17. THUẬT TOÁN DUYỆT ĐỒ THỊ 1. DUYỆT THEO CHIỀU RỘNG Độ phức tạp thời gian Trường hợp xấu nhất, BFS phải duyệt tất cả đường đi tới các đỉnh. Độ phức tạp thời gian xấp xỉ O(bd) Tính đầy đủ BFS có tính đầy đủ vì nó sẽ tìm tất cả các đỉnh không phân biệt loại đồ thị (vô hướng, có hướng, có trọng số…). 19 KHOA CÔNG NGHỆ THÔNG TIN
  18. THUẬT TOÁN DUYỆT ĐỒ THỊ 2. DUYỆT THEO CHIỀU SÂU Duyệt theo chiều sâu (Depth-First Search) đồ thị vô hướng. A B C Xuất phát từ đỉnh A D E 20 KHOA CÔNG NGHỆ THÔNG TIN
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
2=>2