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 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. nội dung chi tiết. | Bài 14: Đồ thị (1/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 1. Đồ thị và các khái niệm liên quan Định nghĩa: Đồ thị Không phải là đồ thị hàm số! Đồ 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, .
