所谓有权图,就是图中的每一条边上都会有相应的一个或一组值。通常情况下,这个值只是一个数字
如:在交通运输网中,边上的权值可能表示的是路程,也可能表示的是运输费用(显然二者都是数字)。不过,边上的权值也有可能是其它东西,比如说是一个字符串,甚至是一个更加复杂的数据包,里面集合了更多的数据
克鲁斯卡尔算法的核心思想是:在带权连通图中,不断地在边集合中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树。
克鲁斯卡尔算法的执行步骤:
第一步:在带权连通图中,将边的权值排序;
第二步:判断是否需要选择这条边(此时图中的边已按权值从小到大排好序)。判断的依据是边的两个顶点是否已连通,如果连通则继续下一条;如果不连通,那么就选择使其连通。
第三步:循环第二步,直到图中所有的顶点都在同一个连通分量中,即得到最小生成树。
关于有权图的实现,看如下实例:
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 < vexs.length; i++) { for (int j = 0; j < vexs.length; j++) { graph.edges[i][j] = A[i][j]; } } } /* * 输出图 */ public void printGraph(Graph graph) { for (int i = 0; i < graph.thevexs.length; i++) { for (int j = 0; j < graph.thevexs.length; j++) { //没有路径则输出/ if (graph.edges[i][j]==-1) { System.out.printf("%4s","/"); } else { System.out.printf("%4d",graph.edges[i][j]); } } System.out.println("\n"); } } }
算法:
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 < e; i++) { temp=E[i]; j=i-1; while (j>=0&&temp.weight<E[j].weight) { E[j+1] = E[j]; j--; } E[j+1] = temp; } } public KruSkal(Graph graph) { int i,j,u1,v1,sn1,sn2,k; int[] vset = new int[100]; Edge[] E = new Edge[100]; k=0; for (i=0;i<graph.thevexs.length;i++) { for (j=0;j<=i;j++) { E[k] = new Edge(); if (graph.edges[i][j]>0) { E[k].start=i; E[k].end=j; E[k].weight=graph.edges[i][j]; k++; } } } SortEdge(E, k); for (i=0;i<graph.thevexs.length;i++) { vset[i]=i; } k=1; j=0; while (k<graph.thevexs.length) { u1=E[j].start; v1=E[j].end; sn1=vset[u1]; sn2=vset[v1]; if (sn1!=sn2) { System.out.printf("(%d,%d),权值:%d",u1,v1,E[j].weight); System.out.println("\n"); k++; for (i=0;i<graph.thevexs.length;i++) { if (vset[i]==sn2) { vset[i]=sn1; } } } j++; } } }
测试类:
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语言基于无向有权图实现克鲁斯卡尔算法代码示例的全部内容,希望对大家有所帮助。有什么问题可以随时留言,小编尽力为您答复。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:notice#cainiaojc.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。