Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 13 - Hoàng Thị Điệp (p2)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 13: Đồ thị" cung cấp cho người học các kiến thức: Đi qua/duyệt đồ thị, sắp xếp topo trên đồ thị đị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,. . | HK I, 2012-2013 Bài 13: Đồ thị (P2) Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Mục tiêu bài học 1. Đồ thị và các khái niệm liên quan 2. Cài đặt đồ thị 3. Một số bài toán tiêu biểu 3.1. Đi qua/duyệt đồ thị • BFS, DFS 3.2. Sắp xếp topo trên đồ thị định hướng không có chu trình 3.3. Tìm đường đi ngắn nhất • Từ một đỉnh nguồn • Giữa mọi cặp đỉnh 3.4. Tìm cây bao trùm ngắn nhất • Prim • Kruskal 4. Đồ thị và C++ diepht@vnu INT2203/w15 2 3.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ểu diễn bởi DAG. Ví dụ: – Quan hệ thứ tự bộ phận trên một tập A – Quan hệ thứ tự thời gian c giữa các nhiệm vụ trong một đề án – Quan hệ thứ tự thời gian giữa các môn học trong một chương trình .