tailieunhanh - Bài giảng Cơ sở dữ liệu giải thuật: Bài 13 - Đồ thị (Phần 2)
Bài giảng Cơ sở dữ liệu giải thuật: Bài 13 - Đồ thị (Phần 2) trình bày về đồ thị và các khái niệm liên quan, cài đặt đồ thị, một số bài toán tiêu biểu (đ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), đồ thị và C++. | 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 . i qua/duy t th • BFS, DFS . 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 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. diepht@vnu th và C++ 2 . 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 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 h c diepht@vnu i tư ng có th bi .
đang nạp các trang xem trước