最小生成树
最小生成树
问题描述
最小生成树算法用于在带权无向图中找到一棵权值和最小的生成树，包括Kruskal、Prim等算法。
Kruskal算法
算法思想
- 基于并查集实现
- 按边权值排序
- 适用于稀疏图
- 时间复杂度
代码实现
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算法
算法思想
- 基于贪心策略
- 从一个顶点开始生长
- 适用于稠密图
- 时间复杂度
或
代码实现
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 | ||
| Prim | ||
| Boruvka |
应用场景
- 网络设计
- 电路布线
- 集群连接
- 管道铺设
- 成本优化
注意事项
- 图的连通性
- 边权非负性
- 重边处理
- 自环处理
- 并查集优化
常见变形
- 次小生成树
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
- 最小瓶颈路径
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
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
投递腾讯等公司6个岗位
