void dfs(int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) dfs(v);
}
}
4.2 广度优先搜索（BFS）
类似树的层序遍历，使用队列实现
void bfs(int start) {
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
🚦 五、最短路径算法
5.1 Dijkstra 算法（正权图）
vector<int> dijkstra(int start) {
vector<int> dist(n, INF);
priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
5.2 Bellman-Ford 算法（可处理负权）
时间复杂度 O(VE)，可检测负环
5.3 Floyd-Warshall 算法（多源最短路径）
三重循环，适用于图顶点不多的场景
时间复杂度 O(n³)
🕸️ 六、图的其他经典算法
6.1 拓扑排序（有向无环图 DAG）
// Kahn 算法，使用入度统计实现
queue<int> q;
vector<int> topo;
for (int i = 0; i < n; i++)
if (indegree[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (int v : adj[u]) {
if (--indegree[v] == 0)
q.push(v);
}
}
发表回复