Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 7 - Nguyễn Khánh Phương

Chương 7 - Đồ thị. Trong chương này, người học có thể hiểu được một số kiến thức cơ bản về: Một số khái niệm cơ bản của đồ thị, biểu diễn đồ thị, các thuật toán duyệt đồ thị, một số ứng dụng của tìm kiếm trên đồ thị. Mời các bạn cùng tham khảo để biết thêm các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 7 - Nguyễn Khánh Phương TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Cấu trúc dữ liệu và giải thuật an th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt Course outline Chương 1. Các kiến thức cơ bản om Chương 2. Thuật toán đệ quy .c Chương 3. Các cấu trúc dữ liệu cơ bản ng co Chương 4. Cây an Chương 5. Sắp xếp th ng Chương 6. Tìm kiếm o du Chương 7. Cấu trúc dữ liệu đồ thị u cu 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co an Chương 7. Cấu trúc dữ liệu đồ thị th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt Các ứng dụng thực tế của đồ thị • Có tiềm năng ứng dụng trong nhiều lĩnh vực: – Mạng máy tính om – Mạng giao thông .c – Mạng điện ng – Mạng cung cấp nước co – Lập lịch an – Tối ưu hóa luồng, thiết kế mạch th ng – Phân tích gen DNA o – Trò chơi máy tính du – Thiết kế hướng đối tượng u cu – …. NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt N i dung 1. Một số khái niệm cơ bản của đồ thị om 2. Biểu diễn đồ thị .c 3. Các thuật toán duyệt đồ thị ng co 4. Một số ứng dụng của tìm kiếm trên đồ thị an th o ng du u cu 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt N i dung 1. Một số khái niệm cơ bản của đồ thị om 2. Biểu diễn đồ thị .c 3. Các thuật toán duyệt đồ thị ng co 4. Một số ứng dụng của tìm kiếm trên đồ thị an th o ng du u cu 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1. Một số khái niệm cơ bản của đồ thị 1.1. Đồ thị vô hướng và có hướng om 1.2. Một số khái niệm cơ bản trên đồ thị .c 1.3. Một số dạng đồ thị đặc biệt ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt Đồ thị vô hướng (Undirected Graphs) Định nghĩa. Đơn (đa) đồ thị vô hướng G = (V,E) là cặp gồm: • Tập đỉnh V là tập hữu hạn phần tử, các phần tử gọi là các đỉnh om • Tập c ...