Kruskal算法计算最小生成树

Kruskal算法计算最小生成树

package com.data.struct;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;import java.util.Random;import com.data.struct.GraphicDepthFirstSort.Node;public class Kruskal { private Node[] list; private List edges=new ArrayList(); public Kruskal(int v,int e){ System.out.println("v:"+v+" e:"+e); list=new Node[v]; for(int i=0;i() { @Override public int compare(Edge o1, Edge o2) { if(o1.w>o2.w){ return 1; }else if(o1.w"); while(node.next!=null){ System.out.print(node.next.id+"("+node.next.w+")=>"); node=node.next; } System.out.println(); } } public void print(){ Node h = list[0]; while(h.treeParent!=null){ h=h.treeParent; } this.print(0, h); } private void print(int level, Node node){ for (int i = 0; i < level; i++) { System.out.format(" "); } System.out.format("|"); for (int i = 0; i < level; i++) { System.out.format("-"); } System.out.format("%d%n", node.id); List child = node.children; for(int i=0;iy.rank){ y.parent=x; }else{ x.parent=y; if(x.rank==y.rank){ y.rank++; } } } public Node findSet(Node x){ if(x.parent!=x){ x.parent=findSet(x.parent); } return x.parent; } public static class Node{ private int id; private Node next; private int w; private int rank; private Node parent; private Node treeParent; private List children=new ArrayList(); } private class Edge{ private Node start; private Node end; private int w; } public static void main(String[] args) { Kruskal k=new Kruskal(5,10); k.printG(); System.out.println("total weight:"+k.kruskal()); k.print(); }}

生成树的结果打印可能不准，weight计算正确

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。