Đồ thị là cấu trúc dữ liệu phi tuyến tính, bao gồm số hữu hạn nút và tập cạnh nối các cặp nút.
Đồ thị dùng để giải quyết bài toán thực tế như biểu diễn mạng lưới. Trong các mạng xã hội, đồ thị được sử dụng.
Trong phần này sẽ bao gồm:
- Kiểm tra đồ thị hai liên thông (Bi-Connected Graph Checking)
- Tìm kiếm theo chiều rộng (BFS) cho đồ thị
- Cầu trong đồ thị (Bridges in a Graph)
- Kiểm tra đồ thị có phải cây không
- Liên thông trong đồ thị có hướng
- Tìm kiếm theo chiều sâu (DFS) cho đồ thị
- Phát hiện chu trình trong đồ thị vô hướng
- Phát hiện chu trình trong đồ thị có hướng
- Chu trình Euler trong đồ thị có hướng
- Đường đi và Chu trình Euler (Eulerian Path and Circuit)
- Thuật toán Fleury
- Tô màu đồ thị (Graph Coloring)
- Kiểm tra đồ thị hai phần (Bipartite)
- Đường đi dài nhất trong đồ thị có hướng không chu trình
- Đường đi ngắn nhất trong đồ thị có hướng không chu trình
- Ghép đôi hai phần tối đa (Maximum Bipartite Matching)
- Đường đi ngắn nhất với đúng k cạnh
- Bài toán Rắn và Thang (Snake and Ladder)
- Đồ thị liên thông mạnh (Strongly Connected Graphs)
- Thuật toán Tarjan cho thành phần liên thông mạnh
- Sắp xếp topo (Topological Sorting)
- Bao truyền tĩnh của đồ thị (Transitive closure)
- Thuật toán Ford-Fulkerson
- Kiểm tra đồ thị sao (Star Graph)
- Thuật toán Bellman-Ford cho đường đi ngắn nhất