javakruskal的简单介绍
本篇文章给大家谈谈javakruskal，以及对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
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(); }}
贪婪算法几个经典例子
问题一：贪心算法的例题分析 例题1、[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品 A B C D E F G重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg价值 10$ 40$ 30$ 50$ 35$ 40$ 30$分析：目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi 64输出一个解，返回上一步骤c--（x,y) ← c计算(x,y）的八个方位的子结点，选出那些可行的子结点循环遍历所有可行子结点，步骤c++重复2显然⑵是一个递归调用的过程，大致如下：C++程序： #define N 8void dfs(int x,int y,int count){ int i,tx,ty; if(countN*N) { output_solution();输出一个解 return; } for(i=0; i
问题二：收集各类贪心算法（C语言编程）经典题目 tieba.baidu/...tb=on百度的C语言贴吧。 全都是关于C的东西。
问题三：几种经典算法回顾 今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解-递归求解-合并 divide-and-conquer(P) { if ( | P |
问题四：求三四个贪心算法的例题（配源程序代码，要带说明解释的）！非常感谢 贪心算法的名词解释
baike.baidu/view/298415
第一个贪心算法 （最小生成树）
baike.baidu/view/288214
第二个贪心算法 （Prim算法）
baike.baidu/view/671819
第三个贪心算法 （kruskal算法）
baike.baidu/view/247951
算法都有详细解释的
问题五：求 Java 一些经典例子算法 前n项阶乘分之一的和
public class jiecheng {
public static void main(String[] args)
{
double sum=0;
double j=1;
int n=10;
for(int i=1;i 问题六：关于编程的贪心法 定义
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
[编辑本段]贪心算法的基本思路
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[编辑本段]例题分析
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi
问题七：求解一贪心算法问题 最快回答那个不懂别乱说，别误人子弟。
这题标准的贪心算法，甚至很多时候被当做贪心例题
要求平均等待时间，那么就得用 总等待时间 / 人数
所以只用关心总等待时间，
如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。
给你写了个，自己看吧。
#include stdafx.h
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin n;
for(int i = 0; i arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i 问题八：分治算法的应用实例 下面通过实例加以说明： 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法求出。算法如下：void maxmin1(int A[],int n,int *max,int *min){ int i;*min=*max=A[0];for(i=0;i *max) *max= A[i];if(A[i]
问题九：回溯算法的典型例题 八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
问题十：什么是算法，都什么，举个例子，谢谢 算法就是解决问题的具体的方法和步骤，所以具有以下性质：
1、有穷性： 一个算法必须保证执行有限步之后结束（如果步骤无限，问题就无法解决）
2、确切性：步骤必须明确，说清楚做什么。
3、输入：即解决问题前我们所掌握的条件。
4、输出：输出即我们需要得到的答案。
5、可行性：逻辑不能错误，步骤必须有限，必须得到结果。
算法通俗的讲：就是解决问题的方法和步骤。在计算机发明之前便已经存在。只不过在计算机发明后，其应用变得更为广泛。通过简单的算法，利用电脑的计算速度，可以让问题变得简单。
kruskal算法java实现，哪位大神能帮忙调通这段代码！
算法如何，就不懂了。但，代码已经正常编译、运行 了
import java.util.*;
import java.io.*;
public class KruskalTest{
private static final int m=3501981;//边数
private static final int n= 2647; //顶点数
private static int[] parent = new int[n];//parent数组,长度为顶点数
private static ArrayListEdge list;//序列
private static float sum = 0; //最小生成树边权总和
public static void main(String[] args)throws FileNotFoundException{
new KruskalTest().test();
}
public void test()throws FileNotFoundException{
File file=new File(".\\Euclidean distance.xlsx");
//读取文件
Scanner sc= new Scanner(file);
double number;
list = new ArrayListEdge();
for(int i=1;i=n;i++)
for(int j=i;j=n;j++) {
Edge edge= new Edge();
edge.u=i;
edge.v=j;
if(sc.hasNext()) {
number=sc.nextDouble();
edge.w=number;
} list.add(edge);
}
Collections.sort(list, new ComparatorEdge(){
@Override
public int compare(Edge o1, Edge o2){
return (int)(o1.w - o2.w);
}
});
//for(int i = 0;i list.size();i++){
// Edge edge = list.get(i);
// System.out.println(edge.u + " " + edge.v + " " + edge.w) ;
// }
kruskal();
System.out.println("the length of MST is " + sum);
}
static void upset(){
for(int i = 0;i n;i++)
parent[i] = -1;
}
int find(int x){
int s;
for(s = x;parent[s] = 0;s = parent[s]);
while(s != x){
int tmp = parent[x];
parent[x] = s;
x = tmp;
}return s;
}
void union(int R1,int R2){
int r1 = find(R1);
int r2 = find(R2);
int temp = parent[r1] + parent[r2];
if(parent[r1] parent[r2]){
parent[r1] = r2;
parent[r2] = temp;
}else{
parent[r2] = r1;
parent[r1] = temp;
}
}
void kruskal(){
int num = 0;
int u ,v;
upset();
for(int i = 0;i m;i++){
Edge edge = (Edge)list.get(i);
u = edge.u;
v = edge.v;
if(find(u) != find(v)){
sum += edge.w;
union(u, v);
num ++;
}
if(num = n - 1)break;
}
}
class Edge{
int u,v;
double w;
}
}
javakruskal的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于、javakruskal的信息别忘了在本站进行查找喔。