DFS (Depth-First Search)
Duyệt đồ thị theo chiều sâu. Dùng stack (hoặc đệ quy).
Độ phức tạp:
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);
}
def dfs(u, adj, visited):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v, adj, visited)
Ứng dụng: Phát hiện chu trình, sắp xếp topo, thành phần liên thông.
BFS (Breadth-First Search)
Duyệt đồ thị theo chiều rộng. Dùng hàng đợi. Tìm đường ngắn nhất trên đồ thị không trọng số.
Độ phức tạp:
vector<int> bfs(int src, vector<vector<int>>& adj) {
int n = adj.size();
vector<int> dist(n, -1);
queue<int> q;
dist[src] = 0; q.push(src);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u])
if (dist[v] == -1) { dist[v] = dist[u]+1; q.push(v); }
}
return dist;
}
Dijkstra — Đường đi ngắn nhất (trọng số không âm)
Độ phức tạp: với priority queue.
vector<long long> dijkstra(int src, vector<vector<pair<int,int>>>& adj) {
int n = adj.size();
vector<long long> dist(n, LLONG_MAX);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[src] = 0; pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [w, v] : adj[u])
if (dist[u]+w < dist[v]) { dist[v] = dist[u]+w; pq.push({dist[v], v}); }
}
return dist;
}
Bellman-Ford — Đường đi ngắn nhất (cho phép trọng số âm)
Độ phức tạp: . Phát hiện được chu trình âm.
vector<long long> bellman_ford(int src, int n, vector<tuple<int,int,int>>& edges) {
vector<long long> dist(n, LLONG_MAX);
dist[src] = 0;
for (int i = 0; i < n-1; i++)
for (auto [u, v, w] : edges)
if (dist[u] != LLONG_MAX && dist[u]+w < dist[v])
dist[v] = dist[u]+w;
// Kiểm tra chu trình âm
for (auto [u, v, w] : edges)
if (dist[u] != LLONG_MAX && dist[u]+w < dist[v])
cout << "Có chu trình âm!";
return dist;
}
Floyd-Warshall — Đường đi ngắn nhất mọi cặp đỉnh
Độ phức tạp: . Phù hợp khi .
// dist[i][j] = đường đi ngắn nhất từ i đến j
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
Kruskal — Cây khung nhỏ nhất (MST)
Độ phức tạp: .
sort(edges.begin(), edges.end()); // {weight, u, v}
DSU dsu(n);
long long mst_cost = 0;
for (auto [w, u, v] : edges)
if (dsu.unite(u, v)) mst_cost += w;
Sắp xếp topo (Topological Sort)
Sắp xếp các đỉnh của DAG theo thứ tự tuyến tính. Dùng thuật toán Kahn (BFS).
vector<int> topo_sort(int n, vector<vector<int>>& adj) {
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] == 0) 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] == 0) q.push(v);
}
return order; // nếu order.size() < n thì có chu trình
}
Bình luận