tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - Đỗ Bích Diệp

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 8: Cấu trúc đồ thị" cung cấp cho các bạn sinh viên các kiến thức: Các khái niệm cơ bản, biểu diễn đồ thị, duyệt đồ thị, bài toán áp dụng. Đây là một tài liệu hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu tham khảo và nghiên cứu. | Câu trúc dữ liệu và Giải thuật Cấu trúc dữ liệu và Giải thuật SFO LAX DFW Chương VIII Câu trúc Đồ thị Đỗ Bích Diệp - Khoa CNTT Chương VIII Đồ thị Nội dung 1. Các khái niệm cơ bản 2. Biểu diễn đồ thị 1. Ma trận lân cận 2. Danh sách lân cận 3. Duyệt đồ thị 4. Bài toán áp dụng 1. Tìm cây khung cực tiểu 2. Tìm đường đi ngắn nhât 3. Bài toán bao đóng truyền ứng 4. Bài toán sắp xếp tô pô Đỗ Bích Diệp - Khoa CNT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 1 Cấu trúc dữ liệu và Giải thuật Đồ thị - Một đồ thị G V E trong đó V tập các đỉnh vertices E tập các cung edges nối các đỉnh trong V - Một cung e u v là một cặp đỉnh - Ví dụ V a b c d e E a b a c a d b e c d c e MÍ _ _ Đỗ Bích Diệp - Khoa CNTT Các khái niệm liên quan - Đồ thị có hướng và Đồ thị vô hướng Trong một cung thứ tự của các đỉnh là quan trọng Cung u v khác với cung v u Trong một cung thứ tự của các đỉnh là không quan trọng Cung u v cũng giống như cung v u Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 2 Câu trúc dữ liệu và Giải thuật Các khái niệm liên quan Bậc của một đỉnh Degree Là số cung kề với đỉnh - Trong một đồ thị có hướng một đỉnh có thể có Bậc trong in-degree Bậc ngoài out-degree - Ví dụ Đỉnh 1 có bậc 3 Đỉnh 1 có bậc trong là 1 và bậc ngoài là 2 Đỗ Bích Diệp - Khoa CNTT Các khái niệm liên quan Đỉnh lân cận Adjacent vertices Trong đồ - Trong đồ thị 1 2 là lân cận của nhau 1 3 là lân cận của nhau Cung kề Incident edges - Nếu có cung u v thì cung này là cung kề của hai đỉnh u và v Đỗ Bích Diệp - Khoa CNT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN