Lý thuyết đồ thị - CT175

---

Lý thuyết

• Các khái niệm quan trọng
• Các phương pháp duyệt đồ thị
• Tính liên thông mạnh trong đồ thị - Giải thuật Tarjan
• Giải thuật tìm đường đi ngắn nhất - Moore-Dijkstra - Bellman-Ford
• Xếp hạng đồ thị và bài tập ví dụ
• Cây vô hướng

Các cấu trúc dữ liệu cần sử dụng để thực hành

• Danh sách - LIST
• Hàng đợi - QUEUE
• Ngăn xếp - STACK

Hướng dẫn phần thực hành các buổi

• Hướng dẫn thực hành - Buổi 1
• Hướng dẫn thực hành - Buổi 2
• Hướng dẫn thực hành - Buổi 3
• Hướng dẫn thực hành - Buổi 4
• Hướng dẫn thực hành - Buổi 5.1
• Hướng dẫn thực hành - Buổi 5.2

Thực hành buổi 1

• Bài 1 - Ma trận đỉnh - cung(add_edge)
• Bài 2 - Ma trận đỉnh - cung(Neighbors)
• Bài 3 - Ma trận đỉnh - đỉnh(Degree)
• Bài 4 - Bậc lớn nhất
• Bài 5.1 - Danh sách cung
• Bài 5.2 - Danh sách cung có điều kiện
• Bài 6 - Đọc đồ thị từ tập tin

Thực hành buổi 2

• Bài 1.1 - Duyệt đồ thị theo chiều rộng(QUEUE)
• Bài 1.2 - Duyệt đồ thị theo chiều sâu(STACK)
• Bài 1.3 - Duyệt đồ thị theo chiều sâu(RECURSION) - Đệ qui
• Bài 2.1 - Duyệt & dựng đồ thị theo chiều rộng(QUEUE)
• Bài 2.2 - Duyệt & dựng đồ thị theo chiều sâu(STACK)
• Bài 2.3 - Duyệt & dựng đồ thị theo chiều sâu(RECURSION) - Đệ qui
• Bài 3 - Đồ thị liên thông - Qua đảo
• Bài 4 - Tôn ngộ không
• Bài 5 - Kiểm tra chu trình - Đồ thị vô hướng
• Bài 6 - Thuyền trưởng Hadoock
• Bài 7 - Phân chia đội bóng
• Bài 8.1 - Kiểm tra tính liên thông mạnh
• Bài 8.2 - Đếm số bộ phận liên thông mạnh
• Bài 9 - Come and go

Thực hành buổi 3

• Bài 1.1 - Tìm đường đi ngắn nhất - đơn đồ thị có hướng
• Bài 1.2 - Tìm đường đi ngắn nhất - đơn đồ thị vô hướng
• Bài 2.1 - Kiểm tra chu trình âm - đơn đồ thị có hướng
• Bài 2.2 - Ứng dụng đường đi ngắn nhất - Ngưu Lang Chức Nữ
• Bài 3 - Ứng dụng đường đi ngắn nhất - Đất nước CyberGraph
• Bài 4 - Ứng dụng đường đi ngắn nhất - Mê cung số
• Bài 5 - Giải thuật Bellman - Ford - tìm đường đi ngắn nhất
• Bài 6 - Giải thuật Bellman - Ford - Kiểm tra chu trình âm
• Bài 7 - Tìm số đường đi ngắn nhất - Nâng cao
• Chú ý quan trọng trong buổi 3

Thực hành buổi 4

• Bài 1 - Xếp hạng đồ thị
• Bài 2 - Bài toán thực tế - Cân đá
• Bài 3 - Bài toán thực tế- Chia kẹo
• Bài 4 - Tổ chức thi công - Dự án xây nhà
• Bài 5.1 - Tổ chức thi công - Dự án phần mềm 1
• Bài 5.2 - Tổ chức thi công - Dự án phần mềm 2

---

Made by Nguyen Huu Nhan