核心内容摘要
精品就去干
Prim算法是一种用于求解最小生成树的经典贪心算法它从一个顶点开始逐步扩展生成树每次选择连接当前生成树与图其余部分的最小权边直到所有顶点都被包含在内。
下面详细解释其原理、步骤和Python实现。
算法核心思想Prim算法基于贪心策略每一步都选择当前看来最优的边。
其核心思想是维持两个顶点集合一个是最小生成树顶点集U另一个是尚未加入生成树的顶点集V-U。
算法不断寻找连接这两个集合的最小权边将该边及其在V-U中的顶点加入最小生成树。
算法步骤如下表所示步骤操作描述1初始化任选一个顶点作为起始点加入集合U。
此时U中只有一个顶点V-U包含其余顶点。
2查找最小边在所有连接U和V-U的边中选择权值最小的边(u, v)其中u∈U, v∈V-U。
3扩展生成树将顶点v加入集合U边(u, v)加入最小生成树边集。
4重复重复步骤2和3直到U包含所有顶点即UV此时最小生成树构建完成。
第一步初始化v, e list(map(int, input().strip().split())) graph [[10001] * (v
for _ in range(v
] for _ in range(e): x, y, w list(map(int, input().strip().split())) graph[x][y] w graph[y][x] w # 因为是无向图需要对称赋值 visited [False] * (v
# 标记顶点是否已加入生成树 minDist [10001] * (v
# 记录每个顶点到当前生成树的最小距离graph使用邻接矩阵表示图。
10001被用作无穷大的近似值表示初始时顶点间不可达。
visited初始时所有顶点都未访问。
minDist初始时所有顶点到生成树的距离为10001无穷大。
第二步启动生成树代码的主循环for _ in range(1, v
会执行v次。
第一次循环具有特殊的启动作用。
当第一次进入循环时所有visited[j]均为False所有minDist[j]均为10001。
因此第一个被选中的顶点cur是编号为1的顶点因为索引从1开始且min_val初始为10002第一个顶点j1的minDist[1]是10001满足条件。
随后执行visited[cur] True意味着顶点1被选为生成树的根节点。
接下来的循环是关键的数据准备for j in range(1, v
: if visited[j] False and minDist[j] graph[cur][j]: minDist[j] graph[cur][j]这段代码更新了所有未被访问的顶点j到当前生成树目前只有顶点1 的距离。
如果顶点j与顶点1之间有边即graph[1][j]小于10001那么minDist[j]就被更新为这条边的权值。
这为下一轮选择新的顶点做好了准备第三步循环构建生成树从第二次循环开始算法进入标准流程选择新顶点min_val 10002 cur -1 for j in range(1, v
: if visited[j] False and minDist[j] min_val: cur j min_val minDist[j]这部分代码遍历所有未访问顶点找出minDist值最小的那个顶点cur。
这个minDist[cur]对应的边就是连接已访问集合和未访问集合的权值最小的边。
找到后将cur标记为已访问。
更新距离for j in range(1, v
: if visited[j] False and minDist[j] graph[cur][j]: minDist[j] graph[cur][j]在将新顶点cur加入生成树后生成树集合扩大了。
这时需要检查对于所有未被访问的顶点j新加入的顶点cur是否给它们提供了一条更短的通往生成树的路径即graph[cur][j]是否小于它们当前记录的最小距离minDist[j]。
如果是则更新minDist[j]为这条更短边的权值。
第四步计算总权重并输出ans 0 for i in range(2, v
: # 注意从2开始 ans minDist[i] print(ans)循环结束后minDist[i]i从2到v存储的就是各个顶点除根节点外加入生成树时所带来的那条最小边的权值。
将它们求和即得到最小生成树的总路径长度。
为什么从2开始累加 因为顶点1是根节点它加入生成树时没有引入边minDist[1]在第一次循环后被置为0但未被计入总和。
从顶点2开始每个顶点加入时对应的最小边权值都被正确记录在minDist中。
核心逻辑与示例为了直观地理解下表模拟了算法在一个简单图上的前几步操作假设图有顶点1,2,3,4边权如下
:2,
:4,
:1,
:3。
循环次数已选顶点cur当前visited集合更新后的minDist数组索引
本轮选择依据最小边初始-{}[10001, 10001, 10001, 10001]-第1次1{1}[0, 2, 4, 10001]选择顶点1作为根第2次2{1, 2}[0, 2, 1, 10001]边(1,
权2第3次3{1, 2, 3}[0, 2, 1, 3]边(2,
权1第4次4{1, 2, 3, 4}[0, 2, 1, 3]边(3,
权3最终总权重ans minDist[2] minDist[3] minDist[4] 2 1 3 6。
时间复杂度该实现的时间复杂度为 O(V²)。
这是因为外层循环v次内层有两个顺序执行的循环各循环v次。
这种复杂度在顶点数V不大或图非常稠密边数E接近V²时是可行的。
对于稀疏图可以使用优先队列最小堆进行优化将时间复杂度降至 O(E log V)克鲁斯卡尔算法是求解最小生成树的经典算法它采用贪心策略通过每次选择权值最小的边并确保不形成环路来构建最小生成树。
以下是对你提供的Kruskal算法Python代码的详细解析。
算法核心思想Kruskal算法的核心是按边权升序处理避免成环。
其步骤如下步骤操作描述1将图中所有边按权值从小到大排序。
2初始化一个空的边集用于存放最小生成树的边。
3遍历排序后的边若当前边加入生成树不会形成环则将其加入。
4重复步骤3直到生成树中包含V-1条边V为顶点数。
算法的关键在于高效判断是否成环这通过并查集 数据结构实现。
代码结构解析
并查集数据结构并查集通过find和join操作管理节点的连通性是避免环路的核心。
n 10001 # 预设最大节点数 father list(range(n)) # 初始化父节点数组 def init(): global father father list(range(n)) # 重置父节点为自身 def find(u): if u ! father[u]: father[u] find(father[u]) # 路径压缩 return father[u] def join(u, v): u find(u) v find(v) if u ! v: father[v] u # 合并两个集合路径压缩在find过程中将节点直接指向根节点降低后续查询复杂度。
集合合并join操作将两个节点所属集合合并若根节点不同则不会形成环。
Kruskal算法主体def kruskal(v, edges): edges.sort(keylambda edge: edge.val) # 按边权排序 init() # 初始化并查集 result_val 0 # 存储最小生成树总权值 for edge in edges: x find(edge.l) y find(edge.r) if x ! y: # 若两个端点不属于同一集合 result_val edge.val # 累加权值 join(x, y) # 合并集合 return result_val排序边使用Python内置排序时间复杂度为O(E log E)。
贪心选择遍历边仅当边两端点不属于同一连通分量即x ! y时将其加入生成树。