写一个图的算法(二)

写一个图的算法(二)

有权图的最小生成树Krusk算法

Kruskal算法计算有权无向图的最小生成树

测试用例：

8 16
4 5 .35
4 7 .37
5 7 .28
0 7 .16
1 5 .32
0 4 .38
2 3 .17
1 7 .19
0 2 .26
1 2 .36
1 3 .29
2 7 .34
6 2 .40
3 6 .52
6 0 .58
6 4 .93

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class KruskalMST {
	//有权图
	static List totallist;
	//最小生成树
	static List minTree;
	static int[] rank;
	static int[] parent;
	static double mstWeight;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int M = scanner.nextInt();
		totallist = new ArrayList();
		minTree = new ArrayList();
		rank = new int[N];
		parent = new int[N];
		for(int i=0;i