蓝桥杯复习，最短路径，库鲁斯卡尔算法

算法简介

代码

import java.util.ArrayList;/*** 	克鲁斯卡尔算法* 	这里的部分代码是从数据结构 图的那里复制过来的* @author 楠**/
public class KruskalDemo {public static void main(String[] args) {/*** 	克鲁斯卡尔算法解题的步骤* 	将路径进行排序（从小到大）* 	按从顺序从路径的集合中取出边（如果取出边不构成回路那么这条边就是最短路径中的一条边）*/creatGraph();setEdgesList(edges);shortEdges(edges, list);}static int[][] edges;// 图的邻接矩阵static ArrayList<Integer[]> list;//图的边的集合，已经排序好的static int[] next;//用来存储结点的终点是哪个，每一个位置就是图中的一个点，每个点存储，这个点的下一个点是哪个/*** 	传入图的邻接矩阵和边的集合* 	输出最短路径* @param edges * @param list*/public static void shortEdges(int[][] edges, ArrayList<Integer[]> list) {ArrayList<Integer[]> result=new ArrayList<>();//最短路径的集合while(list.size()!=0) {Integer[] temp = list.remove(0);if(check(temp)) {result.add(temp);}}//输出最短路径选择的顺序for(int i=0;i<result.size();i++) {System.out.println(result.get(i)[0]+"\t"+result.get(i)[1]+"\t"+result.get(i)[2]);}}/*** 	约定* 		终点的终点，没有终点，就是0* 		在这个方法中我们也保证了一定是小的点指向大的点*	是否构成回路 * 		不构成回路的条件是新加入的两个点的终点不是同一个点、* @param temp* @return*/public static boolean check(Integer[] temp) {int a = temp[0];while (next[a] != 0) {a = next[a];}int b = temp[1];while (next[b] != 0) {b = next[b];}if(a==b&&a!=0) {return false;}next[temp[0]]=temp[1];return true;}/*** * @param edges	给定图的邻接矩阵* @return	返回图的边，按边的权值从小打到返回*/public static ArrayList<Integer[]> setEdgesList(int[][] edges) {list =new ArrayList<>();for(int i=0;i<edges.length;i++) {for(int j=i+1;j<edges.length;j++) {if(edges[i][j]>0) {Integer[] temp=new Integer[3];temp[0]=i;temp[1]=j;temp[2]=edges[i][j];int m=0;while(m<list.size()&&temp[2]>list.get(m)[2]) {m++;}list.add(m, temp);}}}return list;}/*** 	创建图的邻接矩阵* 	约定* 		可以访问是大于0,大于0表示两个点之间的路径* 		不可以访问为0* 		我们使用下标来代替点（A B C D E F G）的标识* @return*/public static int[][] creatGraph() {edges= new int[7][7];next=new int[edges.length];// A   B   C   D   E  F   Gedges[0] = new int[] { 0,  12, 0,  0,  0, 16, 14 };edges[1] = new int[] { 12, 0,  10, 0,  0, 7,  0 };edges[2] = new int[] { 0,  10, 0,  3,  5, 6,  0 };edges[3] = new int[] { 0,  0,  3,  0,  4, 0,  0 };edges[4] = new int[] { 0,  0,  5,  4,  0, 2,  8 };edges[5] = new int[] { 16, 7,  6,  0,  2, 0,  9 };edges[6] = new int[] { 14, 0,  0,  0,  8, 9,  0 };return edges;}}