如何做转运网站,推荐几个没封的网站2021,学校网站建设机构,如何优化基础建站1. 前言
克鲁斯卡尔算法#xff08;Kruskals algorithm#xff09;是一种用于寻找加权图的最小生成树#xff08;Minimum Spanning Tree, MST#xff09;的经典算法。这种算法是由约瑟夫克鲁斯卡尔#xff08;Joseph Kruskal#xff09;提出的#xff0c;并且适用于所有…1. 前言
克鲁斯卡尔算法Kruskals algorithm是一种用于寻找加权图的最小生成树Minimum Spanning Tree, MST的经典算法。这种算法是由约瑟夫·克鲁斯卡尔Joseph Kruskal提出的并且适用于所有类型的加权无向图特别是那些边比较稀疏的图。 Prim算法更偏重于图的顶点而克鲁斯卡尔算法更偏重于图的边。 2. 基本步骤
排序首先将图中的所有边按照权重cost从小到大进行排序。初始化创建一个空集合来保存最小生成树中的边。遍历边依次检查每一条边检查顺序基于权重的大小。对于每一条边 (u, v)如果加入这条边不会在已选择的边中形成环则将这条边加入到最小生成树中。如果加入这条边会导致环的形成则跳过这条边。终止条件重复上述过程直到最小生成树包含了 n - 1 条边其中 n 是顶点的数量或者没有更多的边可以添加为止。
3. 代码
public class Kruskal {// 静态内部类static class Edge implements ComparableEdge{// 顶点集合,构造器赋值用于toString方法ListVertex vertices;// 下列两属性是定点集合的索引比如索引0代表顶点v1int start;int end;int weight;public Edge(int start, int end, int weight) {this.start start;this.end end;this.weight weight;}public Edge(ListVertex vertices, int start, int end, int weight) {this.vertices vertices;this.start start;this.end end;this.weight weight;}Overridepublic int compareTo(Edge o) {return Integer.compare(this.weight, o.weight);}Overridepublic String toString() {return v vertices.get(start).name vvertices.get(end).name ( weight );}}public static void main(String[] args) {ListVertex vertices new ArrayList();Vertex v1 new Vertex(0);Vertex v2 new Vertex(1);Vertex v3 new Vertex(2);Vertex v4 new Vertex(3);Vertex v5 new Vertex(4);Vertex v6 new Vertex(5);Vertex v7 new Vertex(6);vertices.add(v1);vertices.add(v2);vertices.add(v3);vertices.add(v4);vertices.add(v5);vertices.add(v6);vertices.add(v7);ListEdge edges new ArrayList();// 由于处理的是加权无向图所以start:0, end:1与start:1, end:0无区别edges.add(new Edge(vertices, 0, 1, 2));edges.add(new Edge(vertices, 0, 2, 4));edges.add(new Edge(vertices, 0, 3, 1));edges.add(new Edge(vertices, 1, 3, 3));edges.add(new Edge(vertices, 1, 4, 10));edges.add(new Edge(vertices, 2, 3, 2));edges.add(new Edge(vertices, 2, 5, 5));edges.add(new Edge(vertices, 3, 4, 7));edges.add(new Edge(vertices, 3, 5, 8));edges.add(new Edge(vertices, 3, 6, 4));edges.add(new Edge(vertices, 4, 6, 6));edges.add(new Edge(vertices, 5, 6, 1));//将边的集合按照从小到大的顺序排列PriorityQueueEdge queue new PriorityQueue(edges);kruskal(vertices.size(), queue);}public static void kruskal(int size, PriorityQueueEdge queue) {// 创建一个空集合来保存最小生成树中的边。ListEdge list new ArrayList();// 最小生成树的顶点数为size个所以只需要找到size-1条边即可while (list.size() size - 1){// 弹出边权重最小的边判断Edge poll queue.poll();// 并查集:用来判断该边加入是否会相交如果会则跳过该边DisjointSet set new DisjointSet(size);int i set.find(poll.start);int j set.find(poll.end);// 如果不相交if(i ! j){list.add(poll);// 将两点相交set.union(i, j);}}for (Edge e : list){System.out.println(e);}}
}输出
v0v3 (1)
v5v6 (1)
v2v3 (2)
v0v1 (2)
v1v3 (3)
v0v2 (4)
4. 图注
初始时顶点图: 最小生成树的图: 由图当v3-v4(v4-v7) v7-v6三顶点已经连通判断(v3-v6)时find(2) find(5)即两个顶点已经连通(如果加入该边会形成环)所以跳过该边。
