锐客网

  1. 首页 > 睿知 > it技术 > >

最小生成树java源代码 最小生成树java源代码是什么

算法IT技术

kruskal算法的代码实现 MST-KRUSKAL(G，w)
function Kruskal(w,MAX)
%此程序为最小支撑树的Kruskal算法实现
%w为无向图的距离矩阵，故为对称矩阵
%MAX为距离矩阵中∞的实际输入值
%时间：2011年6月22日0:07:53
len=length(w); %图的点数
edge=zeros(len*(len-1）,3）; %用于存储图中的边
count=1; %图中的边数
for i=1:len-1 %循环距离矩阵，记录存储边
for j=i 1:len
if w(i,j)~=MAX
edge(count,1）=w(i,j);
edge(count,2）=i;
edge(count,3）=j;
count=count 1;
end
end
end
edge=edge（1:count-1,:); %去掉无用边
[tmp,index]=sort(edge(:,1）); %所有边按升序排序
i=3; %其实测试边数为3条（3条以下无法构成圈，即无需检测）
while 1
x=findcycle(edge(index（1:i),:),len); %检测这些边是否构成圈
if x
index(i)=0; %若构成圈 ， 则将该边对应的index项标记为0，以便除去
else
i=i 1; %若没有构成圈，则i加1，加入下一边检测
end
index=index(index0); %将构成圈的边从index中除去
if i==len
break; %找到符合条件的点数减一条的边，即找到一个最小支撑树
end
end
index=index（1:len-1）; %截短index矩阵，保留前len-1项
%%%%%%%%%%%% 结果显示 %%%%%%%%%%%%%
s=sprintf('\n\t%s\t%s\t %s\t','边端点','距离','是否在最小支撑树');
for i=1:count-1
edge_tmp=edge(i,:);
if ~isempty(find(index==i,1）)
s_tmp=sprintf('\n \t (%d,%d)\t %d\t %s\t',edge_tmp（2）,edge_tmp（3）,edge_tmp（1）,'√');
else
s_tmp=sprintf('\n \t (%d,%d)\t %d\t %s\t',edge_tmp（2）,edge_tmp（3）,edge_tmp（1）,'×');
end
s=strcat(s,s_tmp);
end
disp(s);
end
function isfind=findcycle(w,N)
%本程序用于判断所给的边能否构成圈：有圈，返回1；否则返回0
%w：输入的边的矩阵
%N：原图的点数
%原理：不断除去出现次数小于2的端点所在的边，最后观察是否有边留下
len=length(w(:,1）);
index=1:len;
while 1
num=length(index); %边数
p=zeros（1,N); %用于存储各点的出现的次数（一条边对应两个端点）
for i=1:num %统计各点的出现次数
p(w(index(i),2）)=p(w(index(i),2）) 1;
p(w(index(i),3）)=p(w(index(i),3）) 1;
end
index_tmp=zeros（1,num); %记录除去出现次数小于2的端点所在的边的边的下标集合
discard=find(p2）; %找到出现次数小于2的端点
count=0; %记录剩余的边数
for i=1:num
%判断各边是否有仅出现一次端点——没有，则记录其序号于index_tmp
if ~(~isempty(find(discard==w(index(i),2）,1）) || ~isempty(find(discard==w(index(i),3）,1）))
count=count 1;
index_tmp(count)=index(i);
end
end
if num==count %当没有边被被除去时，循环停止
index=index_tmp（1:count); %更新index
break;
else
index=index_tmp（1:count); %更新index
end
end
if isempty(index) %若最后剩下的边数为0，则无圈
isfind=0;
else
isfind=1;
end
end
%
% a =[
% 0 3 2 3 100 100 100
% 3 0 2 100 100 100 6
% 2 2 0 3 100 1 100
% 3 100 3 0 5 100 100
% 100 100 100 5 0 4 6
% 100 100 1 100 4 0 5
% 100 6 100 6 100 5 0];
%
% Kruskal(a,100） {
最小生成树的Kruskal算法 。
Kruskal算法基本思想：
每次选不属于同一连通分量（保证不生成圈）且边权值最小的顶点 ， 将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量
排序使用Quicksort(O(eloge))
检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数
Union-Find使用rank启发式合并和路径压缩
总复杂度O(eloge)=O(elogv) （因为en(n-1）/2）
}constmaxn=100;maxe=maxn*maxn;typeedge=recorda,b :integer; //边的2个顶点len :integer; //边的长度end;varedges :array[0..maxe]of edge; //保存所有边的信息p,r :array[0..maxn]of integer; //p保存i的父亲节点，r用来实现Union-Find的rank启发式n,e :integer; //n为顶点数，e为边数procedure swap(a,b:integer); //交换beginedges[0]:=edges[a];edges[a]:=edges[b];edges[b]:=edges[0];end;procedure quicksort(l,r:integer); //快速排序varx,i,j :integer;beginx:=edges[random(r-l 1) l].len;i:=l;j:=r;repeatwhile edges[i].lenx do inc(i);while edges[j].lenx do dec(j);if i=j thenbeginswap(i,j);inc(i); dec(j);enduntil ij;if lj then quicksort(l,j);if ir then quicksort(i,r);end;procedure init;vari :integer;beginassign(input,'g.ini');reset(input);readln(n,e);for i:=1 to e do readln(edges[i].a,edges[i].b,edges[i].len); //从文件读入图的信息for i:=1 to n do p[i]:=i; //初始化并查集randomize;quicksort(1,e); //使用快速排序将边按权值从小到大排列end;function find(x:integer):integer; //并查集的Find，用来判断2个顶点是否属于一个连通分量beginif xp[x] then p[x]:=find(p[x]);find:=p[x]end;procedure union(a,b:integer); //如果不属于且权值最小则将2个顶点合并到一个连通分量vart :integer;begina:=find(a);b:=find(b);if r[a]r[b] then begin t:=a;a:=b;b:=t end;if r[a]=r[b]then inc(r[a]);p[a]:=b;end;procedure kruskal; //主过程varen :integer; //en为当前边的编号count :integer; //统计进行了几次合并 。n-1次合并后就得到最小生成树tot :integer; //统计最小生成树的边权总和begincount:=0;en:=0; tot:=0;while countn-1 dobegininc(en);with edges[en] dobeginif find(a)find(b) thenbeginunion(a,b);writeln(a,'--',b,':',len);inc(tot,len);inc(count);end;end;end;writeln('Total Length=',tot)end;{===========main==========}begininit;kruskal;end.Kruskal算法适用于边稀疏的情形 ， 而Prim算法适用于边稠密的情形 import java.util.ArrayList;import java.util.Collections;class Bian implements Comparable//两点之间的加权边{private int first,second;//表示一条边的两个节点private int value;//权值public Bian(int first,int second,int value){this.first=first;this.second=second;this.value=https://www.04ip.com/post/value;}public int getFirst(){return first;}public int getSecond(){return second;}public int getValue(){return value;}@Overridepublic in tcompareTo(Object arg0){return value((Bian)arg0).value1:(value==((Bian)arg0).value0:-1）;}@Overridepublic String toString(){returnBian[first= first ,second= second ,value= value ];}}class ShuZu{static ArrayListArrayList list=new ArrayListArrayList();//存放每一个数组中的节点的数组static ArrayListArrayList bianList=new ArrayListArrayList();//对应存放数组中的边的数组public static void check(Bianb)//检查在哪个数组中{if(list.size()==0){ArrayListInteger sub=new ArrayListInteger();sub.add(b.getFirst());sub.add(b.getSecond());list.add(sub);ArrayListBian bian=new ArrayListBian();bian.add(b);bianList.add(bian);return;}int first=b.getFirst();int shuyu1=-1;int second=b.getSecond();int shuyu2=-1;for(int i=0;ilist.size();i)//检查两个节点分别属于哪个数组{for(int m=0;mlist.get(i).size();m){if(first==(Integer)list.get(i).get(m))shuyu1=i;if(second==(Integer)list.get(i).get(m))shuyu2=i;}}if(shuyu1==-1shuyu2==-1）//表示这两个节点都没有需要新加入{ArrayListInteger sub=new ArrayListInteger();sub.add(b.getFirst());sub.add(b.getSecond());list.add(sub);ArrayListBianbian=newArrayListBian();bian.add(b);bianList.add(bian);}if(shuyu1==-1shuyu2!=-1）//表示有一个点已经在数组中只把另一个加入就可以了{list.get(shuyu2).add(first);bianList.get(shuyu2）.add(b);}if(shuyu2==-1shuyu1!=-1）//表示有一个点已经在数组中只把另一个加入就可以了{list.get(shuyu1).add(second);bianList.get(shuyu1).add(b);}if(shuyu1==shuyu2shuyu1!=-1）//表述两个在同一个组中会形成环{}if(shuyu1!=shuyu2shuyu1!=-1shuyu2!=-1）//表示两个点在不同的组中需要合并{for(inti=0;ilist.get(shuyu2）.size();i){list.get(shuyu1）.add(list.get(shuyu2）.get(i));}list.remove(shuyu2）;for(inti=0;ibianList.get(shuyu2）.size();i){bianList.get(shuyu1）.add(bianList.get(shuyu2）.get(i));}bianList.get(shuyu1）.add(b);bianList.remove(shuyu2）;}}public static void show(){for(inti=0;ibianList.get(0).size();i)System.out.println(bianList.get(0).get(i));}}public class Test{public static void main(String[] args){ArrayListBian l=new ArrayListBian();l.add(newBian（1,3,1）);l.add(newBian（1,2,6）);l.add(newBian（1,4,5）);l.add(newBian（2,3,5）);l.add(newBian（2,5,3）);l.add(newBian（3,4,5）);l.add(newBian（3,5,6）);l.add(newBian（3,6,4）);l.add(newBian（4,6,2）);l.add(newBian（5,6,6）);Collections.sort(l);//for(inti=0;il.size();i)//System.out.println(l.get(i));for(inti=0;il.size();i)ShuZu.check(l.get(i));ShuZu.show();}}
java 最小生成树public class AbstractGraphV
{
public AbstractGraph(List?extends Edge edges, ListVvertices)
{
}
public static class Edge
{
}
}
public class WeightedGraph extends AbstractGraphFloat
{
public WeightedGraph(ListWeightedEdge edges, ListFloat vertices)
{
super(edges, vertices);
}
public static class WeightedEdge extends Edge
{
}
}
试试这种？
题目1:一个简单的算法演示程序(JAVA语言实现)1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程 。
2. 可以进行手动演示，也可以自动步进式演示 。
3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔 。
4. 不同的算法输入要求见下 。
界面要求：
1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面 。
2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作 。
其他要求：
1. 标识符命名遵循Windows命名规范 。
2. 能够注意各种异常处理，注重提高程序运行效率 。
提交内容：
1. 全部源代码 。
2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）
参考算法：
1. 最小生成树算法：Prim算法、Kruskal算法 。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点 。要求在图形方式下进行演示算法执行步骤 。
2. 单源最短路算法：Dijkstra算法 。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点 。要求在图形方式下进行演示算法执行步骤 。
3. 最优编码算法：Huffman编码算法 。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码 。要求动态列出每个字符的出现概率统计结果以及对应编码 。
4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等 。
用java写了一个最小生成树问题的程序 ， 在进行快速排序边长的权重时 ， 出现了下面的报错说明 edges[] edgelist1= g.listedges(graph1);中最小生成树java源代码的listedges方法有问题
class graph {
public double[][] generate(int n) {
return null;
}
public double[] listlength(double[][] d) {
return null;
}
public edges[] listedges(double [][] d) {
return null;
}
}
全返回null最小生成树java源代码的最小生成树java源代码，最小生成树java源代码，最小生成树java源代码，，，，，，，都还没做
【最小生成树java源代码 最小生成树java源代码是什么】最小生成树java源代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于最小生成树java源代码是什么、最小生成树java源代码的信息别忘了在本站进行查找喔 。

    推荐阅读


    上一篇：小米6安卓7.0隐藏游戏，小米6安卓70隐藏游戏怎么设置

    下一篇：如何制作一个高质量的网页游戏服务器？ 网页游戏服务器怎么制作