您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 怎么用LeetCode找到最小生成树里的关键边和伪关键边
## 引言
在图论中，最小生成树（Minimum Spanning Tree, MST）是一个经典问题。而识别MST中的**关键边**和**伪关键边**则是该问题的进阶应用场景。本文将详细讲解如何通过LeetCode题目（如[1489. 找到最小生成树里的关键边和伪关键边](https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/)）来掌握这一技能。
---
## 目录
1. [基本概念回顾](#基本概念回顾)
2. [问题定义与LeetCode题目分析](#问题定义与leetcode题目分析)
3. [解法思路：暴力法到优化策略](#解法思路暴力法到优化策略)
4. [代码实现与详细注释](#代码实现与详细注释)
5. [复杂度分析与优化验证](#复杂度分析与优化验证)
6. [常见错误与调试技巧](#常见错误与调试技巧)
7. [总结与扩展](#总结与扩展)
---
## 基本概念回顾
### 最小生成树（MST）
- **定义**：连通无向图中权值和最小的生成树。
- **算法**：
- Kruskal算法（基于并查集）
- Prim算法（基于优先队列）
### 关键边与伪关键边
- **关键边**：如果删除这条边后，图的MST权值增大或不连通，则该边为关键边。
- **伪关键边**：该边存在于某些MST中，但不是所有MST的必需边（即不是关键边）。
---
## 问题定义与LeetCode题目分析
### 题目描述
给定一个带权无向图，要求返回：
1. 所有关键边的索引列表。
2. 所有伪关键边的索引列表。
### 示例
**输入**：
n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
**输出**：
关键边: [0, 1] 伪关键边: [2, 3, 4, 5]
---
## 解法思路：暴力法到优化策略
### 步骤1：计算原始MST的权值
使用Kruskal算法计算原始图的MST权值`mst_weight`。
### 步骤2：判断关键边
对于每条边`e`：
1. **排除法**：从图中移除`e`后重新计算MST。
- 如果图不连通或新MST权值 > `mst_weight`，则`e`是关键边。
### 步骤3：判断伪关键边
对于非关键边`e`：
1. **强制包含法**：将`e`预先加入MST，再计算剩余图的MST。
- 如果新MST权值 == `mst_weight`，则`e`是伪关键边。
### 优化点
- **并查集路径压缩**：提升连通性检查效率。
- **边预处理排序**：避免重复排序。
---
## 代码实现与详细注释
```python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return False
if self.rank[x_root] < self.rank[y_root]:
self.parent[x_root] = y_root
else:
self.parent[y_root] = x_root
if self.rank[x_root] == self.rank[y_root]:
self.rank[x_root] += 1
return True
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list[list[int]]) -> list[list[int]]:
# 添加原始索引并排序
edges = [(u, v, w, i) for i, (u, v, w) in enumerate(edges)]
edges.sort(key=lambda x: x[2])
def kruskal(n, edges, exclude_edge=None, include_edge=None):
uf = UnionFind(n)
weight = 0
count = 0
if include_edge is not None:
u, v, w, i = include_edge
if uf.union(u, v):
weight += w
count += 1
for edge in edges:
if exclude_edge is not None and edge[3] == exclude_edge[3]:
continue
u, v, w, i = edge
if uf.union(u, v):
weight += w
count += 1
if count == n - 1:
break
return weight if count == n - 1 else float('inf')
mst_weight = kruskal(n, edges)
critical = []
pseudo_critical = []
for edge in edges:
# 检查是否为关键边
new_weight = kruskal(n, edges, exclude_edge=edge)
if new_weight > mst_weight:
critical.append(edge[3])
continue
# 检查是否为伪关键边
new_weight = kruskal(n, edges, include_edge=edge)
if new_weight == mst_weight:
pseudo_critical.append(edge[3])
return [critical, pseudo_critical]
O(E log E)（排序占主导）。O(E * E α(V))（并查集操作近似常数）。O(E^2 α(V))。O(V)。O(V + E)。UnionFind。”`
本文通过LeetCode实例详细解析了关键边与伪关键边的判定方法，提供了从理论到实践的完整路径。建议读者结合代码实现动手调试以加深理解。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。