- 分析场景
- 图解算法
- 图解回路分析
- 总的来说：要先根据节点来生成图，
- 对生成好的树：得到我们的数据变，进行排序的编写
- 然后还要对我们的判断是否会有回路的的情况
- 最后才是编写我们的算法
- 总的来说步骤有点多，但是不是很复杂的
代码阅读建议
- 首先要明白我们的思想：是用二维数组【也就是矩阵】来进行存放两边是否连通
- 然后就先看我Mgraph类进行一步步的看着走就OK了
public class kruskalDemo {
//用INF来表示两个顶点不能连通
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
char[] vertexs = {'A','B','C','D','E','F','G'};
int matrix[][] = {
/*B*/
{ 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}
};
//创建kruskal的实例
MGraph mGraph = new MGraph(vertexs,matrix);
mGraph.print();
}
}
class MGraph {
//记录边的个数
private int edgeNum;
//顶点数组
private char[] vertexs;
//领接矩阵
private int[][] matrix;
//构造器
public MGraph(char[] vertexs,int[][] matrix) {
//初始化顶点树和边的个数
int vlen = vertexs.length;//表示多少个顶点
//初始化顶点，或者写this.vertexs = vertexs;我这里使用的是拷贝的方式
this.vertexs = new char[vlen];
for (int i = 0; i < vertexs.length; i++) {
this.vertexs[i] = vertexs[i];
}
//初始化边，我这里使用的是拷贝的方式，或者写this.matrix = matrix
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] != Integer.MAX_VALUE) {//说明之间是连通的
edgeNum++;
}
}
}
}
//遍历一下领接矩阵
public void print() {
System.out.println("领接矩阵为：");
System.out.println();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.printf("%15d" , matrix[i][j]);
}
System.out.println();
}
}
}
2、去对边进行排序
（1）编写表示我们边的一个类
//创建一个边类，它的实例表示一条边
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;
}
//后面要显示，便于输出，所以重写toString
@Override
public String toString() {
return "从边" +
"start=" + start +
"到" + end +
"的权值为：" + weight +
'}';
}
}
（2）编写排序方法
- 这里开始有点乱的了，去看MGraph类中的如下方法【有方法一和方法二和方法三】
- getPosition方法：用来获取某一个顶点的下标
- getEdges方法：用来获取我们边的数组【就是我们刚才已经编写好的一个图里面，他们的每一个边都进行统计，方到一个数组里面，进行后续的排序】
- sortEdge：这个就是我们要排序的方法了
class MGraph {
//记录边的个数
private int edgeNum;
//顶点数组
private char[] vertexs;
//领接矩阵
private int[][] matrix;
//构造器
public MGraph(char[] vertexs,int[][] matrix) {
//初始化顶点树和边的个数
int vlen = vertexs.length;//表示多少个顶点
//初始化顶点，或者写this.vertexs = vertexs;我这里使用的是拷贝的方式
this.vertexs = new char[vlen];
for (int i = 0; i < vertexs.length; i++) {
this.vertexs[i] = vertexs[i];
}
//初始化边，我这里使用的是拷贝的方式，或者写this.matrix = matrix
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] != Integer.MAX_VALUE) {//说明之间是连通的
edgeNum++;
}
}
}
}
//遍历一下领接矩阵
public void print() {
System.out.println("领接矩阵为：");
System.out.println();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.printf("%15d" , matrix[i][j]);
}
System.out.println();
}
}
public void sortEdge(EData[] edges) {
for (int i = 0; i < edges.length - 1; i++) {
for (int j = 0; j < edges.length - i - 1; j++) {
if (edges[j].weight > edges[j+1].weight) {
//满足就要交换edges[j].weight > edges[j+1].weight
EData temp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = temp;
}
}
}
}
public EData[] getEdges() {
int index = 0;
EData[] edges = new EData[edgeNum];//因为刚才我们已经统计的边的条数
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
if (matrix[i][j] != Integer.MAX_VALUE) {
edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
}
}
}
return edges;
}
public int getPosition(char ch) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == ch) {//说明找到了
return i;
}
}
return -1;
}
}
（3）来看这一步的测试
看第二部分测试
public class kruskalDemo {
//用INF来表示两个顶点不能连通
public static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
//第一部分是测试第一步
char[] vertexs = {'A','B','C','D','E','F','G'};
int matrix[][] = {
/*B*/
{ 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}
};
//创建kruskal的实例
MGraph mGraph = new MGraph(vertexs,matrix);
mGraph.print();
//第二部分是测试第二部分的
EData[] eData = mGraph.getEdges();//获取我们边的数组
System.out.println("排序前 = " + Arrays.toString(eData));
mGraph.sortEdge(eData);
System.out.println("排序后 = " + Arrays.toString(eData));
}
}
3、确定是否有回边的方法
（1）方法的编写
在类MGraph里面增加一个方法getEnd：这个方法不好理解，但是它的目的在于判断最后的终点，到时候算法好进行处理：如果理解不了，暂时跳过这方法的想象，记住有这么一个方法就可以了
public int getEnd(int[] ends,int i) {
while (ends[i] != 0) {
i = ends[i];
}
return i;
}
（2）到现在总体的方法：理解好思路，准备马上进行算法编写
package cn.mldn.kruskal;
import java.util.Arrays;
public class kruskalDemo {
//用INF来表示两个顶点不能连通
public static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
//第一部分是测试第一步
System.out.println("--------------------------------------------------");
char[] vertexs = {'A','B','C','D','E','F','G'};
int matrix[][] = {
/*B*/
{ 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}
};
//创建kruskal的实例
MGraph mGraph = new MGraph(vertexs,matrix);
mGraph.print();
//第二部分是测试第二部分的
System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++=");
EData[] eData = mGraph.getEdges();//获取我们边的数组
System.out.println("排序前 = " + Arrays.toString(eData));
mGraph.sortEdge(eData);
System.out.println("排序后 = " + Arrays.toString(eData));
//最后一部分的测试了
System.out.println("======================================================");
mGraph.kruskal();
}
}
//创建一个边类，它的实例表示一条边
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;
}
//后面要显示，便于输出，所以重写toString
@Override
public String toString() {
return "从边" +
"start=" + start +
"到" + end +
"的权值为：" + weight +
'}';
}
}
class MGraph {
//记录边的个数
private int edgeNum;
//顶点数组
private char[] vertexs;
//领接矩阵
private int[][] matrix;
//构造器
public MGraph(char[] vertexs,int[][] matrix) {
//初始化顶点树和边的个数
int vlen = vertexs.length;//表示多少个顶点
//初始化顶点，或者写this.vertexs = vertexs;我这里使用的是拷贝的方式
this.vertexs = new char[vlen];
for (int i = 0; i < vertexs.length; i++) {
this.vertexs[i] = vertexs[i];
}
//初始化边，我这里使用的是拷贝的方式，或者写this.matrix = matrix
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] != Integer.MAX_VALUE) {//说明之间是连通的
edgeNum++;
}
}
}
}
//遍历一下领接矩阵
public void print() {
System.out.println("领接矩阵为：");
System.out.println();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.printf("%15d" , matrix[i][j]);
}
System.out.println();
}
}
public void sortEdge(EData[] edges) {
for (int i = 0; i < edges.length - 1; i++) {
for (int j = 0; j < edges.length - i - 1; j++) {
if (edges[j].weight > edges[j+1].weight) {
//满足就要交换edges[j].weight > edges[j+1].weight
EData temp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = temp;
}
}
}
}
public EData[] getEdges() {
int index = 0;
EData[] edges = new EData[edgeNum];//因为刚才我们已经统计的边的条数
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
if (matrix[i][j] != Integer.MAX_VALUE) {
edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
}
}
}
return edges;
}
public int getPosition(char ch) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == ch) {//说明找到了
return i;
}
}
return -1;
}
public int getEnd(int[] ends,int i) {
while (ends[i] != 0) {
i = ends[i];
}
return i;
}
}
4、算法编写
在我们的MGraph里面添加方法五kruskal方法
-
带着这张图去理解
-
代码实现
public void kruskal() {
int index = 0;//表示随后这个结果数组的索引【因为我们最后的数组俩面，要知道它多少条边】
int[] ends = new int[edgeNum];//用于保存“已有最小生成树”中的每一个顶点在最小生成树中的终点
//创建结果数组【将来我们最小生成树是以一个数组，就是最小边的一些集合】
EData[] rets = new EData[edgeNum];
//获取图中所有的边的集合，初始时候一共有12条边【你可以去数一数我们的那个图】
EData[] edges = getEdges();
System.out.println("获取图的边集合为" + edges.length);
//按照边的权值进行从小到大进行排序
sortEdge(edges);
//进行遍历edges了，将边添加到最小生成树里面，并且要判断是否形成回路【即准备加入的边是否构成回路，如果没有变成回路，则加入到rets里面，如果构成就不能加入机器了】
for (int i = 0; i < edgeNum; i++) {
//获取到第i条边的第一个顶点（起点）
int p1 = getPosition(edges[i].start);
//获取到第i条边的第二个顶点
int p2 = getPosition(edges[i].end);
//获取p1这个顶点在已有的最小生成树中的终点是哪个
int m = getEnd(ends,p1);
//获取p2这个顶点在已有的最小生成树中的终点是哪个
int n = getEnd(ends,p2);
//判断是否这个边加入会构成回路
if (m != n) {//m==n说明构成了回路
//设置m在“最小生成树”中的终点
ends[m] = n;
rets[index++] = edges[i];//说明有一条表加入到rets里面的
}
}
//统计并打印最小生成树【说白点就是输出一下rets】，如果有null的话是正确的啊，因为我们在12条边中选几条
for (int i = 0; i < rets.length; i++) {
if (rets[i] != null) {
System.out.println(rets[i]);
}
}
//最后来加一下它们的最小距离
int num = 0;
for (int i = 0; i < rets.length; i++) {
if (rets[i] != null) {
num += rets[i].weight;
//为了好理解
System.out.println(num);
}
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）