Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 14b - Hoàng Thị Điệp (2014)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 14: Đồ thị" cung cấp cho người học các bài toán tiêu biểu về đồ thị như: Đi qua/duyệt đồ thị, sc định hướng không có chu trình, tìm đường đi ngắn nhất, tìm cây bao trùm ngắn nhất. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 14b - Hoàng Thị Điệp (2014)Bài 14: Đồ thị (2/2)Giảng viên: Hoàng Thị ĐiệpKhoa Công nghệ Thông tin – Đại học Công NghệCấu trúc dữ liệu và giải thuậtHKI, 2013-2014Nội dung chínhĐồ thị và các khái niệmliên quan2. Cài đặt đồ thị3. Một số bài toán tiêubiểu1. Đi qua/duyệt đồ thị BFS, DFS Sắp xếp topo trên đồ thịđịnh hướng không cóchu trình2 Tìm đường đi ngắn nhất Từ một đỉnh nguồn Giữa mọi cặp đỉnh Tìm cây bao trùm ngắnnhất Prim Kruskal4. Đồ thị và C++diepht@vnu3.1. Đi qua đồ thị3.2. Sắp xếp topoĐồ thị định hướng không chu trình Thuật ngữ directed acyclic graph (DAG) acyclic digraph Nhiều dạng quan hệ trên một tập đối tượng có thể biểudiễn bởi DAG. Ví dụ: Quan hệ thứ tự bộ phậntrên một tập A Quan hệ thứ tự thời giangiữa các nhiệm vụtrong một đề án Quan hệ thứ tự thời giangiữa các môn họctrong một chương trình học5acbdefdiepht@vnu