Thuật toán đồ thị

Trang này là điểm xuất phát cho nhóm thuật toán đồ thị: hai phép duyệt nền tảng (DFS, sắp xếp topo) được tóm tắt ngay bên dưới, còn mỗi thuật toán lớn có trang riêng với trực giác, ví dụ chạy tay, lỗi thường gặp và bài tập (kể cả đề VOI).

Lộ trình học gợi ý

1. Duyệt đồ thị: DFS (bên dưới), rồi BFS cho đường đi ngắn nhất không trọng số, BFS trên lưới và trên không gian trạng thái.
2. Đường đi ngắn nhất có trọng số: 0-1 BFS khi cạnh chỉ 0/1, Dijkstra khi trọng số không âm, Bellman-Ford và Floyd-Warshall khi có cạnh âm hoặc cần mọi cặp đỉnh.
3. Cây khung và liên thông: Cây khung nhỏ nhất (MST), Bridge và Articulation Point, SCC.
4. Cấu trúc đặc biệt và nâng cao: Đồ thị hàm, Đường đi Euler, 2-SAT.

Các trang trong nhóm

Liên quan: Biểu diễn đồ thị, DSU, DSU có hoàn tác, DP trên đồ thị, Luồng mạng.

DFS: $O(V+E)$

Đi sâu hết mức theo một nhánh rồi quay lui. Dùng để đếm thành phần liên thông, kiểm tra chu trình, tính kích thước cây con, và là nền của cầu/khớp, SCC.

vector<bool> visited(n, false);
void dfs(int u, vector<vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) dfs(v, adj);
}

Với $V$ tới ${10}^5$ trở lên trên đồ thị dạng đường thẳng, đệ quy có thể tràn stack: chuyển sang DFS bằng stack tường minh.

Sắp xếp topo (thuật toán Kahn): $O(V+E)$

Xếp các đỉnh của DAG sao cho mọi cạnh $u\to v$ có $u$ đứng trước $v$. Nếu cuối cùng order có ít hơn $n$ đỉnh thì đồ thị có chu trình.

vector<int> indegree(n, 0);
for (int u=0; u<n; u++) for (int v:adj[u]) indegree[v]++;
queue<int> q;
for (int i=0; i<n; i++) if (!indegree[i]) q.push(i);
vector<int> order;
while (!q.empty()) {
    int u=q.front(); q.pop(); order.push_back(u);
    for (int v:adj[u]) if (!--indegree[v]) q.push(v);
}