Java语言基于无向有权图实现克鲁斯卡尔算法代码示例

作者：袖梨 2022-06-29

所谓有权图，就是图中的每一条边上都会有相应的一个或一组值。通常情况下，这个值只是一个数字

如：在交通运输网中，边上的权值可能表示的是路程，也可能表示的是运输费用（显然二者都是数字）。不过，边上的权值也有可能是其它东西，比如说是一个字符串，甚至是一个更加复杂的数据包，里面集合了更多的数据

克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。

克鲁斯卡尔算法的执行步骤：

第一步：在带权连通图中，将边的权值排序；

第二步：判断是否需要选择这条边（此时图中的边已按权值从小到大排好序）。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。

第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。

关于有权图的实现，看如下实例：

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.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);
	}
}

相关文章

精彩推荐