tailieunhanh - 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

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! | 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 3 KHOA CÔNG NGHỆ THÔNG TIN 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 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 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 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 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 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 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