您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

克鲁斯卡尔算法(图文)

第十三双眼睛2023-10-23【数据结构与算法】人已围观

简介克鲁斯卡尔算法

克鲁斯卡尔算法

package com.xingchen.day017;
import java.util.Arrays;
public class KrusKa {
private int edgesNum;//边的数量
private char[] vertex;//顶点集合
private int[][] matrix;//邻接矩阵
//表示两个顶点不能联通
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
char[] vertext = {'A','B','C','D','E','F','G'};
int[][] matrix = {
{0,12,INF,INF,INF,16,14},
{12,0,10,INF,INF,7,INF},
{INF,10,0,3,5,6,INF},
{INF,INF,3,0,4,INF,INF},
{INF,INF,5,4,0,2,8},
{16,7,6,INF,2,0,9},
{14,INF,INF,INF,8,9,0}
};
KrusKa krusKa = new KrusKa(vertext, matrix);
//krusKa.print();
Edata[] edges = krusKa.getEdges();
//System.out.printf("a" + Arrays.toString(edges));
krusKa.kruskal();

}
public KrusKa(char[] vertex,int[][] matrix) {
int vlen = vertex.length;
this.vertex = new char[vlen];
for (int i = 0; i < vertex.length; i++) {
this.vertex[i] = vertex[i];
}
this.matrix = new int[vlen][vlen];
for (int i = 0; i<vlen ; i++) {
for (int j = 0; j< vlen; j++) {
this.matrix[i][j] = matrix[i][j];
}
}
//统计边
for (int i = 0; i<vlen ; i++) {
for (int j = i+1;j<vlen; j++) {
if (this.matrix[i][j] != INF) {
edgesNum ++;
}
}
}

}
public void kruskal() {
int index = 0;
int[] ends = new int[edgesNum];//用于保存已有生成树中每个顶点在最小生成树中的终点
//创建结果数组,保存最后生成的最小生成树
Edata[] rets = new Edata[edgesNum];
//获取途中所有的边
Edata[] edges = getEdges();
System.out.println(edges.length);
sort(edges);
//遍历edges，判断是否构成回路,如果能构成回路，则不加入，否则加入
for (int i = 0; i<edgesNum; i++) {
int p1 = getPosition(edges[i].start);
int p2 = getPosition(edges[i].end);
//获取p1这个顶点在已有的最小生成树中的终点
int m = getEnd(ends, p1);
int n = getEnd(ends, p2);
if (m != n) {
ends[m] = n;//设置m在已有最小生成树中的终点
rets[index ++] = edges[i];
}
}
System.out.println("最小生成树；" + Arrays.toString(rets));
}
public void print() {
System.out.println("临接矩阵为");
for (int i = 0; i < vertex.length; i++) {
for (int j = 0; j < vertex.length; j++) {
System.out.printf("%12d\t",matrix[i][j]);
}
System.out.println("");
}
}
//对边进行排序
public static void sort(Edata[] edges) {
for (int i = 0; i<edges.length - 1; i++) {
for (int j = 0; j< edges.length - 1; j++) {
if (edges[j].weight > edges[j+1].weight) {
Edata temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
}
}
// 返回顶点的坐标
public int getPosition(char ch) {
for (int i = 0; i<vertex.length; i++) {
if (vertex[i] == ch) {
return i;
}
}
return -1;
}
// 获取图中的边
private Edata[] getEdges() {
int index= 0 ;
Edata[] edges = new Edata[edgesNum];
for (int i = 0;i<vertex.length; i++) {
for (int j = i+1;j<vertex.length;j++) {
if (matrix[i][j] != INF) {
edges[index] = new Edata(vertex[i], vertex[j], matrix[i][j]);
index ++;
}
}
}
return edges;
}
// 获取下标为i的顶点的终点
public int getEnd(int[] ends, int i) {
while (ends[i] != 0) {
i = ends[i];
}
return i;
}
}
//表示一条边
class Edata{
char start;
char end;
int weight;
public Edata (char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public String toString() {
return "Edata{" +
"start=" + start +
", end=" + end +
", weight=" + weight +
'}';
}
}

Tags：

很赞哦！ ()

上一篇：普利姆算法(图文)

下一篇：迪杰斯特拉算法(图文)