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

Bài 13:<br /> <br /> th (P1)<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 /> –<br /> <br /> i qua/duy t<br /> th<br /> • BFS, DFS<br /> – S p x p topo trên<br /> th nh hư ng không có chu trình<br /> – Tìm ư ng i ng n nh t<br /> • T m t nh ngu n<br /> • Gi a m i c p nh<br /> – 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 /> 1.<br /> <br /> diepht@vnu<br /> <br /> th và các khái ni m liên quan<br /> <br /> 3<br /> <br /> nh nghĩa:<br /> •<br /> <br /> th là m t mô hình toán h c<br /> –<br /> <br /> •<br /> <br /> th<br /> <br /> ư c s d ng<br /> bi u di n m t t p<br /> nhau theo m t cách nào ó.<br /> <br /> i tư ng có quan h v i<br /> <br /> nh nghĩa hình th c<br /> –<br /> th G ư c xác nh b i m t c p (V, E), trong ó<br /> – V là t p nh<br /> – E là t p các c nh n i c p nh E ⊆ {(u,v) | u, v ⊆ V}<br /> <br /> •<br /> <br /> th vô hư ng<br /> – quan h<br /> nh nghĩa b i m i c nh là quan h<br /> – E ⊆ {{u,v} | u, v ⊆ V}<br /> <br /> •<br /> <br /> th<br /> <br /> i x ng<br /> <br /> nh hư ng<br /> <br /> – (u, v) ≠ (v, u)<br /> <br /> diepht@vnu<br /> <br /> 4<br /> <br /> diepht@vnu<br /> <br /> 5<br /> <br />