算法简介 代码 import java.util.ArrayList;/*** 克鲁斯卡尔算法* 这里的部分代码是从数据结构 图的那里复制过来的* @author 楠**/public class KruskalDemo {public static void main(String[] args) {/*** 克鲁斯卡尔算法解题的步骤* 将路径进行排序（从小到大）*

思路：严格次小生成树，和最小生成树只有一条边他是不同的，那么利用这一点去写，我们先做最小生成树，然后把最小生成树用到的边建无向图,我们用d1[i][j]表示i点向上跳跃 2 j 2^j 2j个点的最大边权,d2同理表示次大边权，那么次小生成树肯定是用之前没有用的边去替换这里的最大边权或最小边权构成的，我们要替换旧边时，就是替换掉lca(a,b)中的d1,d2中的一个边。 代码： #prag

本篇用于记录我在做图的最短路径的问题过程中学到的算法，如果有不足之处，还请指出。 关于图的最短路径，有四种算法，分别是普利姆算法，迪鲁斯卡尔算法，弗洛伊德算法和贝尔曼福特算法，接下来将对这些算法依次进行讲解。 1.普利姆算法 普里姆算法（Prim算法），是图论中的一种算法，可在加权连通图里搜索最小生成树，也就是求最小权值，最后生成的路径（也就是两个点之间的路径个数）个数比点少一，比如下面的图