这篇文章主要介绍了Java语言基于无向有权图实现克鲁斯卡尔算法代码示例，具有一定参考价值，需要的朋友可以了解下。
所谓有权图，就是图中的每一条边上都会有相应的一个或一组值。通常情况下，这个值只是一个数字
如：在交通运输网中，边上的权值可能表示的是路程，也可能表示的是运输费用（显然二者都是数字）。不过，边上的权值也有可能是其它东西，比如说是一个字符串，甚至是一个更加复杂的数据包，里面集合了更多的数据
克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。
克鲁斯卡尔算法的执行步骤：
第一步：在带权连通图中，将边的权值排序；
第二步：判断是否需要选择这条边（此时图中的边已按权值从小到大排好序）。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。
第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。
关于有权图的实现，看如下实例：
Graph:
package kruskal; public class Graph { final int max=100; /* * 顶点节点 */ public class VexNode{ int adjvex; int data; } VexNode[] vexNodes; int[] thevexs; //顶点集合 int[][] edges = new int[max][max]; //边集合 /* * 创建图 */ public void createGraph(Graph graph,int[][] A,int[] vexs) { thevexs=vexs; for (int i = 0; i 算法：
package kruskal; public class KruSkal { public class Edge{ int start; int end; int weight; } public void SortEdge(Edge[] E,int e) { Edge temp; int j; for (int i = 0; i =0&&temp.weight0) { E[k].start=i; E[k].end=j; E[k].weight=graph.edges[i][j]; k++; } } } SortEdge(E, k); for (i=0;i 测试类：
package kruskal; public class Test { public static void main(String[] args) { int[] vexs = {0,1,2,3,4}; int[][] A = { {0,1,3,4,7}, {1,0,2,-1,-1}, {3,2,0,5,8}, {4,-1,5,0,6}, {7,-1,8,6,0} }; Graph graph = new Graph(); graph.createGraph(graph, A, vexs); graph.printGraph(graph); KruSkal kruSkal = new KruSkal(graph); } }总结
以上就是本文关于Java语言基于无向有权图实现克鲁斯卡尔算法代码示例的全部内容，希望对大家有所帮助。有什么问题可以随时留言，小编尽力为您答复。
以上就是Java语言基于无向有权图实现克鲁斯卡尔算法代码示例的详细内容，更多请关注0133技术站其它相关文章！
