百练百会 bestWit

Appearance

L8_06 图论算法及综合应用 ​

一、最小生成树 ​

1.1 Kruskal算法 ​

cpp
struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

vector<int> parent;
vector<int> rank_;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank_[x] < rank_[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    parent.resize(n);
    rank_.resize(n, 0);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    
    int totalWeight = 0;
    int edgesUsed = 0;
    
    for (const Edge& e : edges) {
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            totalWeight += e.weight;
            edgesUsed++;
            if (edgesUsed == n - 1) break;
        }
    }
    return totalWeight;
}

1.2 Prim算法 ​

cpp
int prim(int n, const vector<vector<pair<int, int>>>& graph) {
    vector<bool> inMST(n, false);
    vector<int> key(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    key[0] = 0;
    pq.push({0, 0});
    
    int totalWeight = 0;
    
    while (!pq.empty()) {
        auto [weight, u] = pq.top();
        pq.pop();
        
        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += weight;
        
        for (auto [v, w] : graph[u]) {
            if (!inMST[v] && w < key[v]) {
                key[v] = w;
                pq.push({w, v});
            }
        }
    }
    return totalWeight;
}

1.3 最小生成树对比 ​

算法时间复杂度适用场景
KruskalO(E log E)稀疏图
PrimO(E + V log V)稠密图

二、最短路径 ​

2.1 Dijkstra算法 ​

cpp
vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> 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] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

2.2 Bellman-Ford算法 ​

cpp
vector<int> bellmanFord(int start, int n, const vector<tuple<int, int, int>>& edges) {
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    
    for (int i = 0; i < n - 1; i++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
            }
        }
    }
    
    // 检测负权环
    for (auto [u, v, w] : edges) {
        if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
            // 存在负权环
        }
    }
    return dist;
}

2.3 Floyd-Warshall算法 ​

cpp
vector<vector<int>> floydWarshall(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> dist = graph;
    
    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] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    return dist;
}

2.4 最短路径算法对比 ​

算法时间复杂度适用场景
DijkstraO((V+E)logV)非负权图
Bellman-FordO(VE)含负权边图
Floyd-WarshallO(V³)稠密图、小规模图

三、图论算法综合应用 ​

3.1 关键路径 ​

cpp
// AOE网的关键路径
vector<int> criticalPath(const vector<vector<int>>& graph, const vector<int>& weights) {
    int n = graph.size();
    vector<int> earliest(n, 0);
    vector<int> latest(n, INT_MAX);
    vector<int> inDegree(n, 0);
    
    // 拓扑排序
    queue<int> q;
    for (int i = 0; i < n; i++) {
        for (int j : graph[i]) {
            inDegree[j]++;
        }
    }
    
    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 : graph[u]) {
            earliest[v] = max(earliest[v], earliest[u] + weights[u]);
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 计算最晚开始时间
    latest[n - 1] = earliest[n - 1];
    for (int i = order.size() - 2; i >= 0; i--) {
        int u = order[i];
        latest[u] = INT_MAX;
        for (int v : graph[u]) {
            latest[u] = min(latest[u], latest[v] - weights[u]);
        }
    }
    
    // 找出关键路径上的节点
    vector<int> critical;
    for (int i = 0; i < n; i++) {
        if (earliest[i] == latest[i]) {
            critical.push_back(i);
        }
    }
    
    return critical;
}

3.2 网络最大流（Ford-Fulkerson） ​

cpp
int fordFulkerson(vector<vector<int>>& graph, int source, int sink) {
    int n = graph.size();
    vector<vector<int>> residual = graph;
    int maxFlow = 0;
    
    while (true) {
        // BFS找增广路径
        vector<int> parent(n, -1);
        queue<int> q;
        q.push(source);
        parent[source] = -2;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v = 0; v < n; v++) {
                if (parent[v] == -1 && residual[u][v] > 0) {
                    parent[v] = u;
                    q.push(v);
                    if (v == sink) break;
                }
            }
        }
        
        if (parent[sink] == -1) break; // 没有增广路径
        
        // 找最小残量
        int pathFlow = INT_MAX;
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            pathFlow = min(pathFlow, residual[u][v]);
        }
        
        // 更新残量网络
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            residual[u][v] -= pathFlow;
            residual[v][u] += pathFlow;
        }
        
        maxFlow += pathFlow;
    }
    
    return maxFlow;
}

3.3 二分图匹配（Hungarian算法） ​

cpp
int hungarian(const vector<vector<int>>& cost) {
    int n = cost.size();
    int m = cost[0].size();
    
    vector<int> u(n + 1, 0);
    vector<int> v(m + 1, 0);
    vector<int> p(m + 1, 0);
    vector<int> way(m + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<int> minv(m + 1, INT_MAX);
        vector<bool> used(m + 1, false);
        
        do {
            used[j0] = true;
            int i0 = p[j0];
            int delta = INT_MAX;
            int j1 = 0;
            
            for (int j = 1; j <= m; j++) {
                if (!used[j]) {
                    int cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }
            
            for (int j = 0; j <= m; j++) {
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }
            
            j0 = j1;
        } while (p[j0] != 0);
        
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0 != 0);
    }
    
    return -v[0];
}

3.4 旅行商问题（TSP） ​

cpp
int tsp(vector<vector<int>>& graph) {
    int n = graph.size();
    int fullMask = (1 << n) - 1;
    vector<vector<int>> dp(n, vector<int>(1 << n, INT_MAX));
    
    dp[0][1] = 0;
    
    for (int mask = 1; mask <= fullMask; mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                int newMask = mask | (1 << v);
                if (dp[u][mask] != INT_MAX) {
                    dp[v][newMask] = min(dp[v][newMask], dp[u][mask] + graph[u][v]);
                }
            }
        }
    }
    
    int minCost = INT_MAX;
    for (int u = 1; u < n; u++) {
        if (dp[u][fullMask] != INT_MAX) {
            minCost = min(minCost, dp[u][fullMask] + graph[u][0]);
        }
    }
    
    return minCost;
}

四、图论算法总结 ​

算法类型算法名称时间复杂度用途
最小生成树KruskalO(E log E)连接所有节点的最小边权和
最小生成树PrimO(E + V log V)连接所有节点的最小边权和
最短路径DijkstraO((V+E)logV)单源最短路径（非负权）
最短路径Bellman-FordO(VE)单源最短路径（含负权）
最短路径Floyd-WarshallO(V³)所有点对最短路径
网络流Ford-FulkersonO(F × E)最大流问题
二分图匹配HungarianO(n³)最优匹配问题
TSPDPO(n² × 2ⁿ)旅行商问题

百炼成钢，融会贯通

© 2026 百练百会（bestwit）GESP备考一站式平台 | 京ICP备16040576号-5