一、克鲁斯卡尔(Kruskal)算法介绍
Kruskal算法用于求加权连通图的最小生成树。
基本思路:按照权重从小到大的顺序选择n-1条边,保证这n-1条边不形成环。
具体方法:首先构造一个只有n个顶点的森林,然后从连通的网络中选择边,按照权重从小到大加入森林,使森林不产生回路,直到森林变成树。
二、连通网的最小生成树理解
在具有n个顶点的连通图中,选择n-1条边组成最小连通子图,使连通子图中n-1条边的权之和最小,称为连通网络的最小生成树。
对于如上图所示的连通网可以有多棵权值总和不相同的生成树。三、克鲁斯卡尔(Kruskal)算法——应用场景(公交站问题)
一个城市增加了七个车站(A、B、C、D、E、F、G),现在需要修路把七个车站连接起来;每个站的距离由边缘线(重量)表示,例如,A-B距离为12公里。问:如何修路才能保证所有站点都能连通,道路总里程最短?(如下图所示)
四、克鲁斯卡尔(Kruskal)算法图解以上图为例,来对克鲁斯卡尔进行演示(假设,用数组R保存最小生成树结果)。
步骤1:连接边缘
第二步:设置边缘
第三步:连接边缘
第四步:附上边缘
第五步:设置边缘
第六步:设置边缘
至此,最小生成树构建完成!它包括以下几个方面:
五、克鲁斯卡尔(Kruskal)算法分析
根据前面介绍的克鲁斯卡尔算法的基本思想和做法,我们可以理解为克鲁斯卡尔算法需要解决以下两个问题:
问题1:根据权重对图的所有边进行排序。
问题2:最小生成树加边时,如何判断是否形成回路?
第一个问题很好解决,可以用排序算法进行排序。
问题2,处理方法是:记录顶点在& # 34;最小生成树& # 34;顶点的终点是& # 34;最小生成树中与它相连的最大顶点& # 34;。然后,每次需要将一条边加入最小生存树时,判断这条边的两个顶点的端点是否重合,如果重合,就会形成一个回路。
六、如何判断是否构成回路——示例说明
在……里
1)c的终点是f。
2)d的终点是f。
3)e的终点是f。
4)f的终点是f。
终点的描述:
1),即所有顶点从小到大依次排列后;顶点的终点是& # 34;与它相连的最大顶点& # 34;。
2),因此,接下来,虽然
七、克鲁斯卡尔(Kruskal)算法——代码实现
包com . RF . data _ structure _ algorithm . algorithm . kruskal;
导入Ja . util . arrays;
/**
* @描述:克鲁斯卡尔算法
* @作者:小智
* @create: 2020-11-16 20:55
*/
公共类KruskalAlgorithm {
int edgeNum//边的数量
char[]顶点;//顶点数组
int[][]矩阵;//邻接矩阵
静态最终int INF = Integer。MAX _ VALUE//用INF表示两个顶点不能连接。
//构造函数
public KruskalAlgorithm(char[]vertexs,int[][] matrix) {
//初始化顶点,复制副本。
this . vertexs = new char[vertexs . length];
for(int I = 0;我& ltvertexs.lengthi++) {
this . vertexs[I]= vertexs[I];
}
//通过复制复制初始化边缘。
this . matrix = new int[vertexs . length][vertexs . length];
for(int I = 0;我& ltvertexs.lengthi++) {
for(int j = 0;j & ltvertexs.lengthj++) {
矩阵[i][j] =矩阵[I][j];
}
}
//计算边的数量。
for(int I = 0;我& ltvertexs.lengthi++) {
for(int j = I+1;j & ltvertexs.lengthj++) {
if (this.matrix[i][j]!= INF) {//可连通,边数为+1。
edge num++;
}
}
}
}
/**
* @描述:打印邻接矩阵。
* @作者:xz
* @日期:2020/11/16 21:11
*/
公共作废打印(){
for(int I = 0;我& ltvertexs.lengthi++) {
for(int j = 0;j & ltvertexs.lengthj++) {
system . out . printf(& # 34;% 12d & # 34,matrix[I][j]);
}
system . out . println();//换行
}
}
/**
* @Description:排序边缘(冒泡排序)
* @Param: edges边集。
* @作者:xz
* @日期:2020/11/16 21:28
*/
public void sort edges(KData[]edges){
for(int I = 0;我& ltedges . length-1;i++){
for(int j = 0;j & ltedges . length-1i;j++){
if(edges[j].重量& gt边缘[j+1]。重量){
KData temp = edges[j];
edges[j]= edges[j+1];
edges[j+1]= temp;
}
}
}
}
/**
* @描述:
* @Param: c表示顶点的值,如’ a ‘和’ b ‘…
* @作者:xz
* @return:返回顶点C的下标,如果找不到则返回-1。
* @日期:2020/11/16 21:35
*/
public int getPosition(char c){
for(int I = 0;我& ltvertexs.lengthi++){
if(vertexs[i] ==c){
返回I;
}
}
//未找到Return -1。
return-1;
}
/**
* @Description:获取图中的边,放入KData[]数组中,通过矩阵邻接矩阵获取。
* kdata[]的形式如下:[[
* @作者:xz
* @日期:2020/11/16 21:41
*/
public KData[] getEdges(){
int index = 0;
KData[]edges = new KData[edge num];
for(int I = 0;我& ltvertexs.lengthi++){
for(int j = I+1;j & ltvertexs.lengthj++){
if(matrix[i][j]!= INF){
edges[index++]= new KData(vertexs[I],vertexs[j],matrix[I][j]);
}
}
}
返回边缘;
}
/**
*函数:获取下标为I的顶点的端点(),用于后面判断两个顶点的端点是否相同。
* @param ends:数组记录每个顶点的终点,ends数组是在遍历的过程中逐渐形成的。
* @param i:表示对应于引入顶点的下标。
* @作者:xz
* @return返回这个顶点对应的端点的下标,下标I。
* @日期:2020/11/16 21:49
*/
private int getEnd(int[] ends,int i) {
while(ends[i]!= 0) {
I = ends[I];
}
返回I;
}
/**
* @描述:克鲁斯卡尔方法
* @作者:xz
* @日期:2020/11/16 21:52
*/
public void kruskal() {
int index = 0;//表示最终结果数组的索引。
int[]ends = new int[edge num];//用来保存& # 34;现有最小生成树& # 34;最小生成树中每个顶点的端点。
//创建结果数组,保存最后一棵最小生成树。
KData[]RETs = new KData[edge num];
//获取图中所有边的集合,共有12条边。
KData[]edges = get edges();
system . out . println(& # 34;图的边集= & # 34;+arrays . tostring(edges)+& # 34;总共& # 34;+edges . length);//12
//根据边的权重排序(从小到大)
sortEdges(边);
//遍历边数组,在向最小生成树添加边时,判断要添加的边是否形成回路,如果不是,则添加rets,否则不能添加。
for(int I = 0;我& ltedgeNumi++) {
//获取第I条边的第一个顶点(起点)。
int p1 = getPosition(edges[i].开始);//p1=4
//获取第I条边的第2个顶点。
int p2 = getPosition(edges[i].end);//p2 = 5
//获取现有最小生成树中顶点p1的端点。
int m = getEnd(ends,P1);//m = 4
//获取现有最小生成树中顶点p2的端点。
int n = getEnd(ends,p2);// n = 5
//是否构成循环?
如果(m!= n) {//不形成循环
ends[m]= n;//将m设置为& # 34;现有最小生成树& # 34;中的终点
RETs[index++]= edges[I];rets数组中添加了一条边。
}
}
//& lt;e,F & gt& ltc,D & gt& ltd,E & gt& ltb,F & gt& lte,G & gt& lt一、B& gt;。
//统计和打印& # 34;最小生成树& # 34;,输出rets。
system . out . println(& # 34;最小生成树为= = = = = = = = = = = = = = = = = = = = & # 34;);
for(int I = 0;我& lt指数;i++) {
system . out . println(RETs[I]);
}
}
/**
* @描述:测试方法
* @作者:xz
* @日期:2020/11/16 21:15
*/
公共静态void main(String[] args) {
//定义7个顶点
char[]vertexs = { & # 39;一& # 39;, 'B&第39名;, 'C & # 39, 'D & # 39, 'E & # 39, 'F & # 39, 'G & # 39};
//定义Kruskar算法的邻接矩阵INF:表示两个顶点不能连接,0表示顶点本身是相互连接的。
int matrix[][] = {
/* A *//* B *//* C *//* D *//* E *//* F *//* G */
/*A*/ {0,12,INF,INF,INF,16,14},
/*B*/ {12,0,10,INF,INF,7,INF},
/*C*/ {INF,10,0,3,5,6,INF},
/*D*/ {INF,INF,3,0,4,INF,INF},
/*E*/ {INF,INF,5,4,0,2,8},
/*F*/ {16,7,6,INF,2,0,9},
/*G*/ {14,INF,INF,INF,8,9,0}
};
//创建KruskalAlgorithm对象的实例。
KruskalAlgorithm KruskalAlgorithm = new KruskalAlgorithm(顶点,矩阵);
//输出构造的邻接矩阵。
system . out . println(& # 34;邻接矩阵= = = = = = = = = = = = \ n & # 34);
kruskalalgorithm . print();
system . out . println();
system . out . println(& # 34;图中的边和权-& # 34;);
KData[]edges = kruskalagriothm . get edges();
system . out . println(& # 34;排序前= & # 34;+arrays . tostring(edges));
kruskalalgorithm . sort edges(edges);
system . out . println(& # 34;排序后= & # 34;+arrays . tostring(edges));
system . out . println();
kruskalalgorithm . kruskal();
}
}
/**
* @Description:创建一个类KData,它的对象实例代表一条边。
* @作者:xz
* @日期:2020/11/16 21:22
*/
KData类{
char开始;//边缘的一个点
char结束;//边缘的另一个点
int重量;//边缘的权重
//构造函数
public KData(char start,char end,int weight) {
this.start = start
this.end = end
this.weight =重量;
}
//重写toString以轻松输出辅助信息。
@覆盖
公共字符串toString() {
return & # 34KData[& lt;"+start+& # 34;, "+end+& # 34;& gt= "+重量+& # 34;]";
}
}
运行:
获取信息的私人消息666
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。