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. . | Bài 14: Đồ thị (2/2) Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014 Nội dung chính Đồ 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 1. Đi qua/duyệt đồ thị BFS, DFS Sắp xếp topo trên đồ thị định hướng không có chu trình 2 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ắn nhất Prim Kruskal 4. Đồ thị và C++ diepht@vnu . Đi qua đồ thị . 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 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 .
