为什么写这个呢?因为那天听到了这个词,属于MST的扩展……最小K度树有空研究。
一.理论准备
需要读者事先懂得prime算法,不太了解的请看博主这一篇http://www.cnblogs.com/hxsyl/p/3286956.html,也需要读者对DP了解一些。
先看一个结论:次小生成树可由最小生成树换一条边得到,笔者认为很有必要搞清楚这一点,,否则对算法理解不够深入。
证明:咱换种方式去看待这个结论(一个生成树可以通过换边得到另一个生成树),T是某一棵最小生成树,T0是任一棵异于T的生成树,通过变换T0 --> T1 --> T2 --> ... --> Tn (T) 变成最小生成树。所谓的变换是,每次把Ti中的某条边换成T中的一条边, 而且树T(i+1)的权小于等于Ti的权。
看下面的具体步骤(一定要理解透彻)。
step 1. 在Ti中任取一条不在T中的边uv.
step 2. 把边uv去掉,就剩下两个连通分量A和B,在T中,必有唯一的边u'v' 连结A和B。这是为什么呢?因为生成树中任意两点间只有一条路径(下面也要用这个),且必有一条。
step 3. 显然u'v'的权比uv小 (prime算法贪心的,否则,uv就应该在T中),把u'v'替换uv即得树T(i+1)。
特别地:取T0为任一棵次小生成树,T(n-1) 也就是次小生成树且跟T差一条边, 结论得证。下面看具体算法。
step 1. 先用prim求出最小生成树T,在prim的同时,用一个矩阵maxd[u][v] 记录 在T中连结任意两点u,v的唯一的路中权值最大的那条边的权值.(有些拗口),这是很容易做到的,因为prim是每次增加一个结点s, 在此需要保存节点和其父节点,采用DP,则最大权值要么是新加入的边,要么是父节点到起始点的采用DP算出来的距离,如下:
//u是刚加入的点,不过还没进入节点数组,v是已经存在的点
//min是按prime新加入那条边
maxd[v][u] = maxd[u][v] = max{min,maxd[father[u]][v]}该步骤用时 O(V^2),就是prime算法的耗时。
step 2. 枚举所有不在T中的边uv, 加入边uv则必然替换权为maxd[u][v]的边,这样才能保证次小。
二.算法实现
以POJ1679为例,判断最小生成树是否唯一(不唯一可能是重边,不过一般在做题里不可能,否则没法建图,另外就是一般情况了,看下图)。
下面这三个图都是MST,权值161。
只要最小生成树和次小生成树权值和一样就唯一。因此得出如下算法,首先计算出最小生成树T,然后对最小生成树上任意不相邻的两个点 uv添加最小生成树以外的存在的边形成环,然后寻找u与v之间最小生成树上最长的边删去,计算map[i][j]与 maxd[i][j差值,求出最小的来,如果是0,就说明MST和次小生成树一样。
//顶点数100,看成了1000,一个MLE,改了立马AC,嘿嘿
//这道题目,AC率很低
import java.util.Scanner;public class POJ1679 {static int maxn = 105;static int[][] map = new int[maxn][maxn];static int[][] maxd = new int[maxn][maxn];static int[] father = new int[maxn];static int[] dist = new int[maxn];static boolean[] vis = new boolean[maxn];static int n,m;public static void main(String[] args) {Scanner sc= new Scanner(System.in);
int num = sc.nextInt();
int u,v,w;
while(num-->0) {
n = sc.nextInt();m = sc.nextInt();for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(i==j) {
map[i][j] = 0;}else {
map[i][j] = 0x3f3f3f3f;}maxd[i][j] = -1;}}for(int i=0; i<m; i++) {u = sc.nextInt();v = sc.nextInt();w = sc.nextInt();map[u][v] = w;map[v][u] = w;}int ans = prime();
int min = 0x3f3f3f3f;
for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {boolean tag = i!=j&&map[i][j]!=0x3f3f3f3f&&father[i]!=j&&father[j]!=i;if(tag) {
if(min>map[i][j]-maxd[i][j]) {
min = map[i][j]-maxd[i][j];}}}}if(0==min) {
System.out.println("Not Unique!");
}else {
System.out.println(ans);}}}private static int prime() {int ans = 0;
for(int i=1; i<=n; i++) {dist[i] = map[1][i];father[i] = 1;vis[i] = false;
}vis[1] = true;
//存放MST节点
int stack[] = new int[n+1];int top = 0;
stack[top++] = 1;for(int i=1; i<n; i++) {int next = 1;
int min = 0x3f3f3f3f;
for(int j=1; j<=n; j++) {if(!vis[j]&&min>dist[j]) {
next = j;min = dist[j];}}vis[next] = true;
ans += min;//dp
for(int k=0; k<top; k++) {maxd[next][stack[k]] = maxd[stack[k]][next]= Math.max(min,maxd[father[next]][stack[k]]);}stack[top++] = next;for(int t=1; t<=n; t++) {if(!vis[t]&&dist[t]>map[next][t]) {
dist[t] = map[next][t];father[t] = next;}}}return ans;
}}接下来该看数据挖掘十大算法了。
- 浏览: 42316 次
最新评论
-
Java_大猫:
LZ 不厚道。转帖 不标识 鄙视
Java版的Quartz表达式生成器,同时适用于Quartz.net(免费下载) -
Java_大猫:
尼玛 LZ 附件呢??
Java版的Quartz表达式生成器,同时适用于Quartz.net(免费下载) -
Leon.Wood:
敢问附件在何方?
Java版的Quartz表达式生成器,同时适用于Quartz.net(免费下载) -
yuxunfeng:
哪来的附件?
Java版的Quartz表达式生成器,同时适用于Quartz.net(免费下载) -
hailong_qin:
求附件啊
Java版的Quartz表达式生成器,同时适用于Quartz.net(免费下载)
相关推荐
探讨了最小生成树的实现问题,分析了基于各种优先队列机制下算法的实现性能,讨论了次小生成树 的性质,提出了时间复杂性为O(n2)的次小生成树算法。
研究内部节点受限的最小生成树问题:给定一个赋权无向完全图[G=V,E],假定[w:E→R ]为边集[E]的权重函数且满足三角不等式,给定点集[V]的一个子集[RR?V],目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小...
标题: 最小生成树 时 限: 1000 ms 内存限制: 10000 K 总时限: 3000 ms 描述: 有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后...
论文研究-运输问题的最小生成树解法.pdf, 运输问题是线性规划中一类特殊类型问题,实际应用很广。本文是叙述运输问题中的平衡情况。以物质调运为例,设A_i为发点i的运出量,B_i为收点j的需要量,C_(ii)为由发点i运至收...
用遗传算法求最小生成树,朱彦廷,,不同的最小生成树代表不同的方案,最好能找出几个最小或次小生成树,以便从中选择,使决策更为科学。本文提出了一个使用遗传算法
本文讨论了针对带权连通图的一种可行性存储结构——单链表结构的构造问题, 并 研究了在该结构上构造最小生成树的算法.
论文研究-求解度约束最小生成树的单亲遗传算法.pdf, 提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机...
在本文中,我们讨论了具有最小直径生成树的简单连接图,使得它们具有相同的支配数。
一种新的最小生成树算法,罗竣友,尤众,本文提出一种新的算法以完成加权连通图的最小生成树(minimum spanning tree, MST)。该算法具有以下优点:1,由于主要以排序为主,因此比较�
基于最小生成树功能脑网络的抑郁症异常属性分析及分类研究,郭浩,闫朋朋,最小生成树是新兴的脑疾病研究手段,已经在脑疾病研究中得到了广泛的应用。本文利用最小生成树的方法来进行功能脑网络的构建,利
摘要:随着天然气输配管网规模的大型化,管网系统进一步优化对提高运行的经济效益和利用率显得非常重要. 采用受限最小生成树算法对城镇燃气管网布局进行优化 ,并将该算
基于最小生成树的配电网故障恢复研究,陈建松,乐秀璠,在简化分析的基础上提出利用图论中的最小生成树来选择配电网供电恢复的最优路径。针对经典的最小生成树算法仅仅只能得到一组最优
针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的min-reduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法...
系统评价是系统工程理论和实践研究中的热点和难点,修正矩阵的层次分析法(CAHP)是系统评价的主要方法之一,是高维多约束的非线性优化问题。在粒子群算法的基础上,设计了节点度不为0的WS型小世界网络作为粒子的...
求最小生成树(简称MST)是一个经典的图论问题,已存在许多近似线性时间复杂度的快速求解算法可以解决。然而,度约束的最小生成树的求解则被证明是一个NP-完全问题,目前仍无法找到多项式时间复杂度的求解算法。本文用...
java算法分析与设计之最小生成树(prim算法)源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少...
为了均衡分簇无线传感器网络节点能量负载,提高网络的能量利用效率,提出了一种粒子寻优和最小生成树聚类规则的能量优化算法(OMST)。该算法为了使得簇头的能量负载能够得到均衡,采用基于粒子寻优的方法来进行适应...
根据Prim最小生成树算法的设计思想,设计了独特CloseEdge型closedge向量表示U到V-U集合中的边,用上三角法建立了无向图的邻接多重双向链表,构造了链接closedge向量和邻接多重双向链表表结点的VU集合双向链。...
图的遍历和生成树求解问题的研究与实现,可以实现图的各种操作
给定具有n个顶点和m个边的简单图G,生成树问题是为给定图G查找生成树。该问题有很多应用,例如电力系统,计算机网络设计和电路分析。 对于一个简单的图,可以使用CRCW PRAM上的O(m + n)个处理器在O(log n)时间内...