09.03_最小生成树

最小生成树

问题描述

最小生成树算法用于在带权无向图中找到一棵权值和最小的生成树，包括Kruskal、Prim等算法。

Kruskal算法

算法思想

基于并查集实现
按边权值排序
适用于稀疏图
时间复杂度 $\mathcal{O}(E \log E)$

代码实现

c++
java
python

class Solution {
public:
    vector<vector<int>> kruskal(int n, vector<vector<int>>& edges) {
        vector<int> parent(n);
        vector<vector<int>> mst;
        
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 按权值排序
        sort(edges.begin(), edges.end(), 
             [](const auto& a, const auto& b) {
                 return a[2] < b[2];
             });
        
        // Kruskal算法
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (find(u, parent) != find(v, parent)) {
                unite(u, v, parent);
                mst.push_back({u, v, edge[2]});
            }
        }
        
        return mst;
    }
    
private:
    int find(int x, vector<int>& parent) {
        if (parent[x] != x) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }
    
    void unite(int x, int y, vector<int>& parent) {
        parent[find(x, parent)] = find(y, parent);
    }
};

class Solution {
    public List<int[]> kruskal(int n, int[][] edges) {
        int[] parent = new int[n];
        List<int[]> mst = new ArrayList<>();
        
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 按权值排序
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        
        // Kruskal算法
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            if (find(u, parent) != find(v, parent)) {
                unite(u, v, parent);
                mst.add(new int[]{u, v, edge[2]});
            }
        }
        
        return mst;
    }
    
    private int find(int x, int[] parent) {
        if (parent[x] != x) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }
    
    private void unite(int x, int y, int[] parent) {
        parent[find(x, parent)] = find(y, parent);
    }
}

class Solution:
    def kruskal(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        parent = list(range(n))
        mst = []
        
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x: int, y: int) -> None:
            parent[find(x)] = find(y)
        
        # 按权值排序
        edges.sort(key=lambda x: x[2])
        
        # Kruskal算法
        for u, v, w in edges:
            if find(u) != find(v):
                unite(u, v)
                mst.append([u, v, w])
        
        return mst

Prim算法

算法思想

基于贪心策略
从一个顶点开始生长
适用于稠密图
时间复杂度 $\mathcal{O}(V^2)$ 或 $\mathcal{O}(E \log V)$

代码实现

c++
java
python

class Solution {
public:
    vector<vector<int>> prim(vector<vector<pair<int, int>>>& adj) {
        int n = adj.size();
        vector<bool> visited(n);
        vector<vector<int>> mst;
        
        priority_queue<pair<int, pair<int, int>>, 
                      vector<pair<int, pair<int, int>>>,
                      greater<>> pq;
        pq.push({0, {0, -1}});
        
        while (!pq.empty()) {
            auto [w, p] = pq.top();
            auto [v, u] = p;
            pq.pop();
            
            if (visited[v]) continue;
            visited[v] = true;
            
            if (u != -1) {
                mst.push_back({u, v, w});
            }
            
            for (auto [next, weight] : adj[v]) {
                if (!visited[next]) {
                    pq.push({weight, {next, v}});
                }
            }
        }
        
        return mst;
    }
};

class Solution {
    public List<int[]> prim(List<List<int[]>> adj) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        List<int[]> mst = new ArrayList<>();
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0, -1});  // weight, vertex, parent
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int w = cur[0], v = cur[1], u = cur[2];
            
            if (visited[v]) continue;
            visited[v] = true;
            
            if (u != -1) {
                mst.add(new int[]{u, v, w});
            }
            
            for (int[] edge : adj.get(v)) {
                int next = edge[0], weight = edge[1];
                if (!visited[next]) {
                    pq.offer(new int[]{weight, next, v});
                }
            }
        }
        
        return mst;
    }
}

class Solution:
    def prim(self, adj: List[List[Tuple[int, int]]]) -> List[List[int]]:
        n = len(adj)
        visited = [False] * n
        mst = []
        
        pq = [(0, 0, -1)]  # weight, vertex, parent
        
        while pq:
            w, v, u = heapq.heappop(pq)
            
            if visited[v]:
                continue
            visited[v] = True
            
            if u != -1:
                mst.append([u, v, w])
            
            for next_v, weight in adj[v]:
                if not visited[next_v]:
                    heapq.heappush(pq, (weight, next_v, v))
        
        return mst

时间复杂度分析

算法时间复杂度空间复杂度

Kruskal	$\mathcal{O}(E \log E)$	$\mathcal{O}(V)$
Prim	$\mathcal{O}(E \log V)$	$\mathcal{O}(V)$
Boruvka	$\mathcal{O}(E \log V)$	$\mathcal{O}(V)$

应用场景

网络设计
电路布线
集群连接
管道铺设
成本优化

注意事项

图的连通性
边权非负性
重边处理
自环处理
并查集优化

常见变形

次小生成树

cpp
java
python

class Solution {
public:
    int secondMST(int n, vector<vector<int>>& edges) {
        vector<vector<int>> mst = kruskal(n, edges);
        int minCost = 0, secondCost = INT_MAX;
        
        for (const auto& e : mst) {
            minCost += e[2];
        }
        
        // 枚举替换每条MST中的边
        for (int i = 0; i < mst.size(); i++) {
            int oldCost = mst[i][2];
            int minReplace = INT_MAX;
            
            // 尝试用非MST中的边替换
            for (const auto& e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (w > oldCost && !inMST(mst, u, v)) {
                    minReplace = min(minReplace, w);
                }
            }
            
            if (minReplace != INT_MAX) {
                secondCost = min(secondCost, minCost - oldCost + minReplace);
            }
        }
        
        return secondCost;
    }
};

class Solution {
    public int secondMST(int n, int[][] edges) {
        List<int[]> mst = kruskal(n, edges);
        int minCost = 0, secondCost = Integer.MAX_VALUE;
        
        for (int[] e : mst) {
            minCost += e[2];
        }
        
        // 枚举替换每条MST中的边
        for (int i = 0; i < mst.size(); i++) {
            int oldCost = mst.get(i)[2];
            int minReplace = Integer.MAX_VALUE;
            
            // 尝试用非MST中的边替换
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (w > oldCost && !inMST(mst, u, v)) {
                    minReplace = Math.min(minReplace, w);
                }
            }
            
            if (minReplace != Integer.MAX_VALUE) {
                secondCost = Math.min(secondCost, minCost - oldCost + minReplace);
            }
        }
        
        return secondCost;
    }
    
    private boolean inMST(List<int[]> mst, int u, int v) {
        for (int[] e : mst) {
            if ((e[0] == u && e[1] == v) || (e[0] == v && e[1] == u)) {
                return true;
            }
        }
        return false;
    }
}

class Solution:
    def secondMST(self, n: int, edges: List[List[int]]) -> int:
        mst = self.kruskal(n, edges)
        min_cost = sum(e[2] for e in mst)
        second_cost = float('inf')
        
        def inMST(mst: List[List[int]], u: int, v: int) -> bool:
            return any((e[0] == u and e[1] == v) or 
                      (e[0] == v and e[1] == u) for e in mst)
        
        # 枚举替换每条MST中的边
        for i in range(len(mst)):
            old_cost = mst[i][2]
            min_replace = float('inf')
            
            # 尝试用非MST中的边替换
            for u, v, w in edges:
                if w > old_cost and not inMST(mst, u, v):
                    min_replace = min(min_replace, w)
            
            if min_replace != float('inf'):
                second_cost = min(second_cost, min_cost - old_cost + min_replace)
        
        return second_cost

最小瓶颈路径

cpp
java
python

class Solution {
public:
    int bottleneckPath(vector<vector<pair<int, int>>>& adj, int start, int end) {
        int n = adj.size();
        vector<bool> visited(n);
        vector<int> maxEdge(n, INT_MAX);
        maxEdge[start] = 0;
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, start});
        
        while (!pq.empty()) {
            auto [w, v] = pq.top();
            pq.pop();
            
            if (v == end) return w;
            if (visited[v]) continue;
            visited[v] = true;
            
            for (auto [u, weight] : adj[v]) {
                if (!visited[u]) {
                    int newMax = max(w, weight);
                    if (newMax < maxEdge[u]) {
                        maxEdge[u] = newMax;
                        pq.push({newMax, u});
                    }
                }
            }
        }
        
        return -1;
    }
};

class Solution {
    public int bottleneckPath(List<List<int[]>> adj, int start, int end) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        int[] maxEdge = new int[n];
        Arrays.fill(maxEdge, Integer.MAX_VALUE);
        maxEdge[start] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, start});
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int w = cur[0], v = cur[1];
            
            if (v == end) return w;
            if (visited[v]) continue;
            visited[v] = true;
            
            for (int[] edge : adj.get(v)) {
                int u = edge[0], weight = edge[1];
                if (!visited[u]) {
                    int newMax = Math.max(w, weight);
                    if (newMax < maxEdge[u]) {
                        maxEdge[u] = newMax;
                        pq.offer(new int[]{newMax, u});
                    }
                }
            }
        }
        
        return -1;
    }
}

class Solution:
    def bottleneckPath(self, adj: List[List[Tuple[int, int]]], start: int, end: int) -> int:
        n = len(adj)
        visited = [False] * n
        max_edge = [float('inf')] * n
        max_edge[start] = 0
        
        pq = [(0, start)]
        
        while pq:
            w, v = heapq.heappop(pq)
            
            if v == end:
                return w
            if visited[v]:
                continue
            visited[v] = True
            
            for u, weight in adj[v]:
                if not visited[u]:
                    new_max = max(w, weight)
                    if new_max < max_edge[u]:
                        max_edge[u] = new_max
                        heapq.heappush(pq, (new_max, u))
        
        return -1