克鲁斯卡尔

一、克鲁斯卡尔(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