CSD201 - Phần 5: Đồ thị

Ứng với CLO5, buổi 29-40. Tương ứng Chương 14 của Goodrich ấn bản 6. Phần khái niệm gồm đồ thị vô hướng và có hướng, đỉnh, cạnh, đỉnh kề, cạnh liên thuộc, bậc, đồ thị liên thông, đồ thị đầy đủ và công thức số cạnh, cùng các ứng dụng thực tế. Phần biểu diễn so sánh ba cấu trúc danh sách cạnh, danh sách kề và ma trận kề theo bộ nhớ và theo chi phí truy vấn. Phần duyệt trình bày tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng, cách cài đặt bằng ngăn xếp và hàng đợi, và khác biệt về ứng dụng của hai phép duyệt. Phần đường đi ngắn nhất trình bày đồ thị có trọng số và thuật toán Dijkstra. Phần cây khung nhỏ nhất trình bày thuật toán Prim-Jarník và thuật toán Kruskal. Khép lại bằng chu trình và đường đi Euler cùng điều kiện cần và đủ, chu trình Hamilton giải bằng quay lui, và tô màu đồ thị bằng thuật toán tô tuần tự.