public class PrimAlgorithm { public static void main(String[] args) {// 测试图是否创建成功char[] data = https://www.it610.com/article/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, 9, 10000, 10000, 3 },{ 7, 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 }, }; // 创建MGraph对象MGraph graph = new MGraph(verxs); // 创建一个MinTree对象MinTree minTree = new MinTree(); minTree.createGraph(graph, verxs, data, weight); // 输出minTree.showGraph(graph); // 测试普利姆算法minTree.prim(graph, 0); }} //创建最小生成树 -> 村庄的图class MinTree { /*** 创建图的邻接矩阵* * @param graph图对象* @param verxs图对应的顶点个数* @param data图的各个顶点的值* @param weight 图的邻接矩阵*/ public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {int i, j; for (i = 0; i < verxs; i++) {graph.data[i] = data[i]; for (j = 0; j < verxs; j++) {graph.weight[i][j] = weight[i][j]; }} } /*** 显示图的邻接矩阵*/ public void showGraph(MGraph graph) {for (int[] link : graph.weight) {System.out.println(Arrays.toString(link)); } }/*** 编写prim算法，得到最小生成树* * @param graph 图* @param v表示从图的第几个顶点开始生成'A' -> 0 'B' -> 1...*/ public void prim(MGraph graph, int v) {// visited[] 标记节点(顶点)是否被访问过int visited[] = new int[graph.verxs]; // visited[] 默认元素的值都是0，表示没有访问过for (int i = 0; i < graph.verxs; i++) {visited[i] = 0; }// 把当前这个节点标记为已访问visited[v] = 1; // h1 和 h2 记录两个顶点的下标int h1 = -1; int h2 = -1; int minWeight = 10000; // 将minWeight初始成一个大数，后面在遍历过程中，会被替换for (int k = 1; k < graph.verxs; k++) {// 因为有graph,verxs顶点,普利姆算法结束后,有graph.verxs -1边// 这个是确定每一次生成的子图，那个节点和这次遍历的节点距离最近for (int i = 0; i < graph.verxs; i++) {// i节点表示被访问过的节点for (int j = 0; j < graph.verxs; j++) {// j节点表示还没有访问过的节点if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {// 替换minWeight(寻找已经访问过的节点和未访问过的节点间的权值最小的边)minWeight = graph.weight[i][j]; h1 = i; h2 = j; }}}// 找到一条边最小System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + ">权值：" + minWeight); // 将当前这个节点标记未已经访问visited[h2] = 1; // minWeight 重新设置为最大值10000minWeight = 10000; } }} class MGraph { int verxs; // 表示图的节点个数 char[] data; // 存放节点数据 int[][] weight; // 存放边，就是邻接矩阵 public MGraph(int verxs) {this.verxs = verxs; data = https://www.it610.com/article/new char[verxs]; weight = new int[verxs][verxs]; }}

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, 0, 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; i < 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); //按照边的权值大小进行排序(从小到大)sortEdges(edges); //遍历edges数组，将边添加到最小生成树中时，判断准备加入的边是否形成了回路，如果没有，就加入rets,否则不能加入for(int i = 0; i < edgeNum; i++) {//获取到第i条边的第一个顶点(起点)int p1 = getPosition(edges[i].start); //获取到第i条边的第2个顶点int p2 = getPosition(edges[i].end); //获取p1这个顶点在已有最小生成树中的终点int m = getEnd(ends, p1); //获取p2这个顶点在已有最小生成树中的终点int n = getEnd(ends, p2); //是否构成回路if(m != n) {//没有构成回路ends[m] = n; //设置m在"已有最小生成树"中的终点 [0,0,0,0,5,0,0,0,0,0,0]rets[index++] = edges[i]; //有一条边加入到rets数组}}//统计并打印"最小生成树",输出retsSystem.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("%20d\t", 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; }}// 找不到，返回-1return -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) {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=" + start + ", end=" + end + ", weight=" + weight + "]"; } }

推荐阅读

• 

  2018世界杯西班牙对摩洛哥哪个厉害 西班牙对摩洛哥预测结果
• 

  做了核酸检测健康码什么时候显示
• 

  说爱你蔡依林mp3下载 如何评价蔡依林唱的说爱你，说爱你 周杰伦
• 

  吉林有哪些特色水果 吉林的水果
• 

  行车记录仪小的好还是大的好 2021年口碑最好的行车记录仪
• 

  东床快婿原本指的是什么 成语东床快婿最初指的是谁
• 

  玩英雄联盟电脑最低配置要求 玩英雄联盟的电脑最低配置是多少
• 

  辛辰和他的 辛辰身世公开了没
• 

  孕妇是否可以吃石榴
• 

  常州轻工学院几个食堂 常州轻工职业技术学院怎么样
• 

  ip前所未有的超高性价比？苹果iPad SE平板曝光
• 

  酷狗音乐如何制作歌词,酷狗歌词制作有报酬么
• 

  实现抵押权申请书
• 

  年轻人头晕晕沉沉是怎么回事 为什么头有点晕
• 

  高德地图如何参加双11集能量_收集能量详细图文教程
• 

  2016office永久激活码教程 正版office2016激活码多少钱
• 

  画圣诞树的软件app，想问一下这个是那个手机指绘软件谢谢大家了
• 

  华为荣耀9怎么样好用吗
• 

  国产手办真的很烂吗 为什么叫手办
• 

  大学生消费调查报告范文精选6篇

• JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
• 事件代理
• Java|Java OpenCV图像处理之SIFT角点检测详解
• java中如何实现重建二叉树
• 数组常用方法一
• 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
• Java|Java基础——数组
• RxJava|RxJava 在Android项目中的使用（一）
• java之static、static|java之static、static final、final的区别与应用
• Java基础-高级特性-枚举实现状态机