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 + "]"; } }

推荐阅读

• 

  2023中山市东凤中学招聘临聘教师4人公告
• 

  京东怎样才能买到正品 京东上的东西都是正品吗
• 

  李宗盛山丘歌词 李宗盛山丘歌曲简介
• 

  聊天室 聊天室哪个
• 

  恳请摄影高手解答一下，这张图片中的星星，是用什么方法拍出来的，怎么效果是一圈一圈的呢？
• 

  数据统计分析师 证书
• 

  尼康s7000电池 尼康7000可以用el15a电池吗
• 

  莓茶叶有什么好处
• 

  算法计算性能分析方法,简述算法的时间复杂度分析方法
• 

  SSD价格为啥降价？如何选购SSD硬盘？
• 

  老人八十大寿庆典活动祝寿词 八十大寿祝寿词
• 

  日本签证需要什么材料 如何办理日本签证
• 

  空调扇不加水可以使用吗
• 

  如何安装代理服务器？ 代理服务器怎么安装
• 

  p20像素是多少（p20配置信息）
• 

  Free玲珑包卫生巾值得入手吗？Free玲珑包卫生巾好用吗
• 

  佳能相机多功能锁开关作用 佳能多功能锁没有用
• 

  运营成本包括哪些内容 运营成本包括哪些
• 

  七律·何畏难
• 

  疫情|疫情又出现了，病毒源头来自哪里？疾控专家的预测八九不离十

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