最小生成树mst性质是什么,最小生成树java代码

　　00-1010 I. prim算法II。克鲁斯卡尔算法

　　00-1010比kruskal具有更高的时间复杂度。

　　流行的解释是：

　　(1)从哪一点生成最小生成树都是一样的，最终的权重都是一样的。

　　(2)从哪个点开始，先将这个点标记为已访问，用已访问数组表示所有节点的访问。

　　(3)在访问节点开始时，从每个非访问节点的距离中选择形成边的最小权重。

　　综合以上三点，是我们prim算法写代码的重要思路。

　　代码实现：

　　包装底漆；导入Java . util . arrays；Class Prim算法{ public static void main(string[]args){//测试看图形是否创建OK char [] data=new char [] {a ， b ， c ， d ， e ， f ， g }；int verxs=data.length//邻接矩阵的关系用一个二维数组表示，大数10000，表示两点不相连int [] [] weight=new int [] {{10000，5，7，10000，10000，10000，2}，{5，10000，10000}。10000, 10000, 10000, 8, 10000, 10000}, {10000, 9, 10000, 10000, 10000, 4, 10000}, {10000, 10000, 8, 10000, 10000, 5, 4}, {10000, 10000, 10000, 4, 5, 10000, 6}, {2, 3, 10000, 10000, 4, 6, 10000},};m graph m graph=new m graph(verxs)；MinTree MinTree=new MinTree()；minTree.createGraph(mGraph，verxs，data，weight)；mintree . showgraph(m graph)；明特里。Prim(mGraph，0)；} } class mintree {/* * Create graph * @ param graph graph对象* @param verxs graph节点号* @param data graph顶点数据值* @param weight graph edge(邻接矩阵)*/public void createGraph(m graph graph，int verxs，char[] data，int[][] weight) { int i，j；for(I=0；i verxsI){ graph . data[I]=data[I]；for(j=0；j verxsj){ graph . weight[I][j]=weight[I][j]；} } } }//显示图public void Show graph(m graph graph){ for(int[]link 3360 graph . weight){ system . out . println(arrays . tostring(link))；}}/* * * Write prim算法* * @ param graph graph object * @ param v将从哪个节点生成最小生成树*/public void PRIM (m graph graph，int v){//定义一个数组确定该节点是否被访问过int[]visited=new int[graph . verxs]；//v这个点已经去过了。从该点访问的访问次数[v]=1；//找到节点下标int h1=-1；int H2=-1；int minWeight=10000//设置

　　义初始值为最大值，只要出现小的就会替换 int sum = 0; // 从1开始循环，相当于就是生成graph.verx - 1条边 for (int k = 1; k < graph.verxs; k++) { for (int i = 0; i < graph.verxs; i++) {//遍历已经访问过的点 if (visited[i] == 1){ for (int j = 0; j < graph.verxs; j++) {//遍历没有访问过的点 //在未访问点中寻找所有与访问过的点相连的边中权值最小值 if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) { minWeight = graph.weight[i][j]; h1 = i; h2 = j; } } } } sum += minWeight; // 求最小生成熟的总权值 //此时已经找到一条边是最小了 System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight); //然后标记点 visited[h2] = 1; //将权值重新变成最大值 minWeight = 10000; } System.out.println("最小生成树的权值是:" + sum); }} // 图class MGraph { int verxs; // 表示图节点个数 char[] data; // 表示节点数据 int[][] weight; // 表示边 public MGraph(int verxs) { this.verxs = verxs; data = new char[verxs]; weight = new int[verxs][verxs]; }}

二、kruskal算法

时间复杂度低一些，但是代码量会大一些

　　对克鲁斯卡尔算法的通俗解释：

　　（1）对每条边的权值进行排序

　　（2）按照从小到大依次选取边构成最小生成树，但是要注意是否构成回路，树的概念是不能生成回路

　　（3）此处用的方法比较巧妙使用了getEnd方法来判断两者终点是不是一样，用ends数组保存最小生成树中每个顶点的终点

　　代码实现：

package Kruskal; import java.util.Arrays; public class KruskalCase { private int edgeNum; //边的个数 private char[] vertexs; //顶点数组 private int[][] matrix; //邻接矩阵 //使用 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[][] = { /*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}}; //大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树. //创建KruskalCase 对象实例 KruskalCase kruskalCase = new KruskalCase(vertexs, matrix); //输出构建的 kruskalCase.print(); kruskalCase.kruskal(); } //构造器 public KruskalCase(char[] vertexs, int[][] matrix) { //初始化顶点数和边的个数 int vlen = vertexs.length; //初始化顶点, 复制拷贝的方式 this.vertexs = new char[vlen]; for (int i = 0; i < vertexs.length; i++) { this.vertexs[i] = vertexs[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) { edgeNum++; } } } } public void kruskal() { int index = 0; //表示最后结果数组的索引 int[] ends = new int[edgeNum]; //用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点 //创建结果数组, 保存最后的最小生成树 EData[] rets = new EData[edgeNum]; //获取图中 所有的边的集合 ， 一共有12边 EData[] edges = getEdges(); System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共" + edges.length); //12 //按照边的权值大小进行排序(从小到大) sortEdges(edges); //遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入 for (int i = 0; i < edgeNum; i++) { //获取到第i条边的第一个顶点(起点) int p1 = getPosition(edges[i].start); //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 //是否构成回路 if (m != n) { //没有构成回路 ends[m] = n; // 设置m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0] rets[index++] = edges[i]; //有一条边加入到rets数组 } } //<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。 //统计并打印 "最小生成树", 输出 rets System.out.println("最小生成树为"); for (int i = 0; i < index; i++) { System.out.println(rets[i]); } } //打印邻接矩阵 public void print() { System.out.println("邻接矩阵为: n"); for (int i = 0; i < vertexs.length; i++) { for (int j = 0; j < vertexs.length; j++) { System.out.printf("%12d", matrix[i][j]); } System.out.println();//换行 } } /** * 功能：对边进行排序处理, 冒泡排序 * * @param edges 边的集合 */ private void sortEdges(EData[] edges) { for (int i = 0; i < edges.length - 1; i++) { for (int j = 0; j < edges.length - 1 - i; j++) { if (edges[j].weight > edges[j + 1].weight) {//交换 EData tmp = edges[j]; edges[j] = edges[j + 1]; edges[j + 1] = tmp; } } } } /** * @param ch 顶点的值，比如A,B * @return 返回ch顶点对应的下标，如果找不到，返回-1 */ private int getPosition(char ch) { for (int i = 0; i < vertexs.length; i++) { if (vertexs[i] == ch) {//找到 return i; } } //找不到,返回-1 return -1; } /** * 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组 * 是通过matrix 邻接矩阵来获取 * EData[] 形式 [[A,B, 12], [B,F,7], .....] * * @return */ private 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] != INF) { edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges; } /** * 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同 * * @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成 * @param i : 表示传入的顶点对应的下标 * @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解 */ private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0] while (ends[i] != 0) { i = ends[i]; } return i; } } //创建一个类EData ，它的对象实例就表示一条边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 "EData [<" + start + ", " + end + ">= " + weight + "]"; } }

到此这篇关于Java实现最小生成树MST的两种解法的文章就介绍到这了,更多相关Java最小生成树内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。