天河建网站,装修公司线上推广方式,宣传部网站建设方案,石家庄网站建设服务前言#xff1a;使用最小生成树的方法解决将所有节点连接起来所需的最小路径问题。
prim算法
Prim算法是一种贪心算法#xff0c;从任意一个顶点开始构建最小生成树。每次选择当前已加入生成树的顶点中#xff0c;距离最近的尚未加入生成树的顶点#xff0c;直到所有顶点…前言使用最小生成树的方法解决将所有节点连接起来所需的最小路径问题。
prim算法
Prim算法是一种贪心算法从任意一个顶点开始构建最小生成树。每次选择当前已加入生成树的顶点中距离最近的尚未加入生成树的顶点直到所有顶点都被加入生成树。
适用场景
稠密图Prim算法在稠密图边数接近 n2 中表现较好因为它的复杂度为O(n^2)其中 n 为节点数量。单源最短路径Prim算法可以从任意一个顶点开始构建最小生成树适合需要从特定顶点开始的情况。
代码实现
prim三部曲 第一步选距离生成树最近节点 第二步最近节点加入生成树 第三步更新非生成树节点到生成树的距离即更新minDist数组
minDist数组 用来记录 每一个节点距离最小生成树的最近距离。由于题目中说了边的权重最大为10000这里将边的最大值初始化为10001。
代码如下
import java.util.*;
public class Main{public static void main (String[] args) {Scanner scannew Scanner(System.in);int vscan.nextInt();int escan.nextInt();int[][] gridnew int[v1][v1];//初始化距离为1001for(int i0;iv;i){Arrays.fill(grid[i],10001);}//根据输入的边的权值建立地图for(int i0;ie;i){int sscan.nextInt();int tscan.nextInt();int kscan.nextInt();grid[s][t]k;grid[t][s]k;}//初始化最小距离为10001int[] minDistnew int[v1];Arrays.fill(minDist,1001);//建立数组判断节点是否在树中boolean[] isInTreenew boolean[v1];//先选择第一个节点加入树中minDist[1]0;//外部循环遍历每一个节点for(int i1;iv;i){int minValInteger.MAX_VALUE;int cur-1;//找到不在树中且距离最近的节点for(int j1;jv;j){if(!isInTree[j] minDist[j]minVal){minValminDist[j];curj;}}//将当前节点加入树中isInTree[cur]true;//更新节点到数的距离主要更新与新加入的节点相连的节点for(int j1;jv;j){if(!isInTree[j] grid[cur][j]minDist[j]){minDist[j]grid[cur][j];}}}//prim算法的循环结束计算路径总和int result0;for(int i2;iv;i){resultminDist[i];}System.out.println(result);}
}注意外部循环是为了确保每个节点都被遍历到。第一个内部循环是找到距离最小生成树最近的节点第二个内部循环是更新minDist。
kruskal算法
Kruskal算法也是一种贪心算法但它是从全局角度出发先将所有边按权重从小到大排序然后依次选择不形成环的边加入生成树直到生成树包含所有顶点。
适用场景
稀疏图Kruskal算法在稀疏图边数远小于 n2中表现较好因为它的复杂度为 nlogn其中n 为边的数量。全局最优Kruskal算法从全局角度出发适合需要考虑所有边的情况。
代码实现
在代码中我们可以使用并查集将两个节点加入同一个集合并判断两个节点是否在同一个集合。 时间复杂度nlogn 快排 logn 并查集 所以最后依然是 nlogn n为边的数量。
代码如下
import java.util.*;
//定义边的类
class Edge{int l,r,val;Edge(int l,int r,int val){this.ll;this.rr;this.valval;}
}public class Main{//题目中节点最多10000所以初始化并查集的节点10001public static int n10001;public static int[] fathernew int[n];public static void init(){for(int i0;in;i){father[i]i;}}public static int find(int u){return ufather[u]?u:(father[u]find(father[u]));}public static void join(int u,int v){ufind(u);vfind(v);if(uv) return;else father[v]u;}public static void main (String[] args) {Scanner scannew Scanner(System.in);int vscan.nextInt();int escan.nextInt();ListEdge edgeListnew LinkedList(); for(int i0;ie;i){int lscan.nextInt();int rscan.nextInt();int valscan.nextInt();edgeList.add(new Edge(l,r,val));}//排序edgeList.sort(Comparator.comparingInt(edge - edge.val));init();int result0;for(Edge edge:edgeList){int xfind(edge.l);int yfind(edge.r);if(x!y){resultedge.val;join(x,y);}}System.out.println(result);}
}
