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

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）

} const  maxn=100;  maxe=maxn*maxn;type  edge=record  a,b :integer; //边的2个顶点  len :integer; //边的长度end;var  edges :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==========}begin  init;  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=value;    }    public int getFirst(){        return first;    }    public int getSecond(){        return second;    }    public int getValue(){        return value;    }    @Override    public in tcompareTo(Object arg0){        return value((Bian)arg0).value1:(value==((Bian)arg0).value0:-1）;    }    @Override    public 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();    }}

相关问答

Q1: 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

    {

        

    }

}

试试这种？

Q2: 题目1:一个简单的算法演示程序(JAVA语言实现)

1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程。

2. 可以进行手动演示，也可以自动步进式演示。

3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔。

4. 不同的算法输入要求见下。

界面要求：

1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面。

2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作。

其他要求：

1. 标识符命名遵循Windows命名规范。

2. 能够注意各种异常处理，注重提高程序运行效率。

提交内容：

1. 全部源代码。

2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）

参考算法：

1. 最小生成树算法：Prim算法、Kruskal算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。

2. 单源最短路算法：Dijkstra算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。

3. 最优编码算法：Huffman编码算法。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。

4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等。

Q3: 用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源代码的信息别忘了在本站进行查找喔。