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: Đồ 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, đồ thị và C++. . | HK I, 2012-2013 Bài 13: Đồ thị (P1) 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. Đồ thị và C++ diepht@vnu INT2203/w14 2 1. Đồ thị và các khái niệm liên quan diepht@vnu INT2203/w14 3 Định nghĩa: Đồ thị • Đồ thị là một mô hình toán học – được sử dụng để biểu diễn một tập đối tượng có quan hệ với nhau theo một cách nào đó. • Định nghĩa hình thức – Đồ thị G được xác định bởi một cặp (V, E), trong đó – V là tập đỉnh – E là tập các cạnh nối cặp đỉnh E ⊆ {(u,v) | u, v ∈ V} • Đồ thị vô hướng – quan hệ định nghĩa bởi mỗi cạnh là quan hệ đối xứng – E ⊆ {{u,v} | u, v ∈ V} • Đồ thị định hướng – (u, v) ≠ (v, .
