Bài giảng Cơ sở dữ liệu giải thuật: Bài 13 - Đồ thị (Phần 2)

Bài 13:<br /> <br /> th (P2)<br /> <br /> Gi ng viên: Hoàng Th i p<br /> Khoa Công ngh Thông tin –<br /> i h c Công Ngh<br /> <br /> M c tiêu bài h c<br /> 1.<br /> th và các khái ni m liên quan<br /> 2. Cài t<br /> th<br /> 3. M t s bài toán tiêu bi u<br /> 3.1. i qua/duy t<br /> th<br /> • BFS, DFS<br /> 3.2. S p x p topo trên<br /> th nh hư ng không có chu trình<br /> 3.3. Tìm ư ng i ng n nh t<br /> • T m t nh ngu n<br /> • Gi a m i c p nh<br /> 3.4. Tìm cây bao trùm ng n nh t<br /> • Prim<br /> • Kruskal<br /> <br /> 4.<br /> diepht@vnu<br /> <br /> th và C++<br /> 2<br /> <br /> 3.1. i qua<br /> <br /> th<br /> <br /> 3.2. S p x p topo<br /> <br /> th<br /> <br /> nh hư ng không chu trình<br /> <br /> • Thu t ng<br /> – directed acyclic graph (DAG)<br /> – acyclic digraph<br /> <br /> • Nhi u d ng quan h trên m t t p<br /> di n b i DAG. Ví d :<br /> – Quan h th t b ph n<br /> trên m t t p A<br /> – Quan h th t th i gian<br /> c<br /> gi a các nhi m v<br /> trong m t<br /> án<br /> – Quan h th t th i gian<br /> gi a các môn h c<br /> trong m t chương trình h c<br /> diepht@vnu<br /> <br /> i tư ng có th bi u<br /> a<br /> <br /> b<br /> <br /> d<br /> <br /> e<br /> <br /> f<br /> <br /> 5<br /> <br />