昆明网站排名优化费用,建设工程规划许可证在哪个网站查询,微信公众平台官网网址,wordpress使用视频教程1.基本概念 生成树#xff1a;连通无向图的生成树是包含图中所有顶点的极小连通子图#xff08;无环#xff09;。 最小生成树#xff1a;所有生成树中边权重总和最小的那棵。
2.常用算法
克鲁斯卡尔算法#xff08;Kruskal#xff09; 步骤#xff1a; 将所有边按权…1.基本概念 生成树连通无向图的生成树是包含图中所有顶点的极小连通子图无环。 最小生成树所有生成树中边权重总和最小的那棵。
2.常用算法
克鲁斯卡尔算法Kruskal 步骤 将所有边按权重升序排序。 依次选择边若其连接两个不同连通分量不形成环则加入生成树。 使用并查集Union-Find高效管理连通性。 时间复杂度O(E log E)排序和并查集操作。 适用场景稀疏图边较少。
普里姆算法Prim 步骤 从任一顶点开始逐步扩展。 每次选择连接已选顶点集和未选顶点集的最小权重边。 使用优先队列如堆维护候选边。 时间复杂度 二叉堆O(E log V) 斐波那契堆O(E V log V)更优。 适用场景稠密图边较多。
3.具体例子
假设有一个无向图包含 4个顶点A, B, C, D 和 6条边权重如下 AB: 权重 1 AC: 权重 3 AD: 权重 4 BC: 权重 2 BD: 权重 5 CD: 权重 6
目标找到该图的最小生成树总权重最小。
1. 克鲁斯卡尔算法Kruskal示例
步骤 按权重升序排序所有边
AB(1) → BC(2) → AC(3) → AD(4) → BD(5) → CD(6) 初始化并查集每个顶点自成一个集合。 依次选择边并检查是否形成环 选择 AB(1)连接 A 和 B不同集合合并集合。 已选边AB(1) 总权重1 顶点集合{A, B}, {C}, {D} 选择 BC(2)连接 B 和 C不同集合合并集合。 已选边AB(1), BC(2) 总权重123 顶点集合{A, B, C}, {D} 选择 AC(3)A 和 C 已属于同一集合形成环跳过。 选择 AD(4)连接 A 和 D不同集合合并集合。 已选边AB(1), BC(2), AD(4) 总权重1247 顶点集合{A, B, C, D}所有顶点连通 此时已选 3 条边V-13算法终止。
最终最小生成树
A — B (1)
B — C (2)
A — D (4)
2. 普里姆算法Prim示例
步骤 从顶点 A 开始初始化优先队列最小堆。 逐步扩展生成树 初始状态已访问顶点 {A}候选边为 A 的邻边 AB(1)、AC(3)、AD(4)。 优先队列AB(1), AC(3), AD(4) 选择 AB(1)连接 A 和 B标记 B 为已访问。 已选边AB(1) 总权重1 候选边更新添加 B 的邻边 BC(2)、BD(5)。 优先队列BC(2), AC(3), AD(4), BD(5) 选择 BC(2)连接 B 和 C标记 C 为已访问。 已选边AB(1), BC(2) 总权重123 候选边更新添加 C 的邻边 CD(6)。 优先队列AC(3), AD(4), BD(5), CD(6) 选择 AC(3)A 和 C 已连通C 已访问跳过。 选择 AD(4)连接 A 和 D标记 D 为已访问。 已选边AB(1), BC(2), AD(4) 总权重1247 所有顶点已访问算法终止。
最终最小生成树
A — B (1)
B — C (2)
A — D (4)
关键结论 克鲁斯卡尔按边权重排序逐步合并不连通的子树。 普里姆从起点扩展每次选择连接已访问和未访问顶点的最小边。 两种算法结果相同因为示例图权重唯一生成的最小生成树唯一。
