算法原理可以参考
勿在浮沙筑高台http://blog.csdn.net/luoshixian099/article/details/51908175
下面是原理的几张图，我觉得非常好，拿过来放这儿供理解呀！
kruskal 添加最小边
prim 添加点
kruskal-添加最小边用了优先级队列，判断联通 和 联通操作用了并查集的思想（路径压缩）
package test;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
class Edge{
int start;
int end;
int weight;
void set(int start,int end,int weight) {
this.start=start;
this.end=end;
this.weight=weight;
}
int getweight(int start,int end) {
return this.weight;
}
Edge(){
}
}
public class MinTreeUF {
public static int find(int p,int[] parent) {
while(parent[p]!=p) {
parent[p]=parent[parent[p]];
p=parent[p];
}
return p;
}
public static boolean isconnect(int p,int q,int[] parent) {
int pr=find(p,parent);
int qr=find(q,parent);
if(pr==qr) {
return true;
}
return false;
}
public static void union(int p,int q,int[] parent) {
if(!isconnect(p,q,parent)) {
int pr=parent[p];
int qr=parent[q];
parent[qr]=pr;
}
}
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
Edge edge[]=new Edge[n];
for(int i=0;i<n;i++) edge[i]=new Edge();
Queue<Edge> pq=new PriorityQueue<>((a,b)->(a.weight-b.weight));
for(int i=0;i<n;i++) {
int p=input.nextInt();
int q=input.nextInt();
int weight=input.nextInt();
edge[i].start=p;
edge[i].end=q;
edge[i].weight=weight;
pq.add(edge[i]);
}
int parent[]=new int[n];
for(int i=0;i<parent.length;i++) {
parent[i]=i;
}
int result=0;
//System.out.println(pq.peek().weight);
while(!pq.isEmpty()) {
Edge e=pq.poll();
int w=e.weight;
//System.out.println(w);
int s=e.start;
int en=e.end;
if(!isconnect(s,en,parent)) {
union(s,en,parent);
result+=w;
System.out.println("w"+w);
}else {
continue;
}
}
System.out.println(result);
}
}
prim
package test;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class MinTree {
public static int minTree(LinkedList<int[]> graph[]) {//最小路径prim
int result=0;
boolean visit[]=new boolean[graph.length];
for(int i=0;i<visit.length;i++) visit[i]=false;
int start=0;
ArrayList<Integer> q=new ArrayList<>();
q.add(start);
visit[start]=true;
int cc=0;
int flag=0;
int min=100;
while(!q.isEmpty())
{
if(flag!=0&&!visit[flag]) {
System.out.println("flag"+flag);
//System.out.println(min);
result+=min;
visit[flag]=true;
}
int c=0;
for(int j=0;j<graph.length;j++) {
q.clear();
if(visit[j]==false) {
for(int i=0;i<graph.length;i++) {
if(visit[i])
q.add(i);
}
break;
}
if(visit[j]==true) {
c++;
}
}
if(c==graph.length) break;
min=100;
flag=0;
//System.out.println(q.size()+" CC"+cc);
for(int i=0;i<q.size();i++) {
int s=q.get(i);
//System.out.println("sssssssss"+s);
LinkedList<int[]> adj=new LinkedList<>();
adj=adjj(graph,s);
// if(!adj.isEmpty())
// min=adj.get(0)[1];
//System.out.println("adj"+adj.size()+" CC"+cc);
for(int j=0;j<adj.size();j++) {
System.out.println(s+" "+adj.get(j)[0]+" "+ adj.get(j)[1]);
if(!visit[adj.get(j)[0]]) {
if(min>adj.get(j)[1]) {
min=adj.get(j)[1];
System.out.println(s+" "+adj.get(j)[0]+" "+ min+" "+cc);
flag=adj.get(j)[0];
}
}
//System.out.println("min:"+min);
//adj.remove(j);
}
//adj.clear();
}
cc++;
}
return result;
}
public static void main(String[] args) {
int v=5;
int edge=3;
int start=0;
Scanner input=new Scanner(System.in);
//System.out.println("please input vertex number");
v=input.nextInt();
start=input.nextInt();
//System.out.println("please input edge number");
edge=input.nextInt();
LinkedList<int[]> graph[]=new LinkedList[v];
for(int i=0;i<v;i++) {
graph[i]=new LinkedList<int[]>();
}
//邻接点，权重
int dist[][]=new int[edge][2];
int weight[]=new int[edge];
//System.out.println("please input edge from start to end");
for(int i=0;i<edge;i++) {
dist[i][0]=input.nextInt();
dist[i][1]=input.nextInt();
weight[i]=input.nextInt();
}
// for(int i=0;i<edge;i++) {
// System.out.println(dist[i][0]);
// System.out.println(dist[i][1]);
// System.out.println(weight[i]);
// }
for(int g=0;g<v;g++)
for(int i=0;i<edge;i++) {
int[] adjw=new int[2];
adjw[0]=dist[i][1];
adjw[1]=weight[i];
if(g==dist[i][0])
graph[dist[i][0]].add(adjw);
}
// for(int i=0;i<graph.length;i++) {
// LinkedList<int[]> gadj=adj(graph,i);
// System.out.println(i);
// for(int j=0;j<gadj.size();j++) {
// System.out.println(gadj.get(j)[0]+" "+gadj.get(j)[1]);
// }
// System.out.println();
// }
int result=minTree(graph);
System.out.println(result);
}
public static LinkedList<int[]> adjj(LinkedList<int[]> graph[],int s){
return graph[s];
}
}
并查集
class UF {
// 连通分量个数
private int count;
// 存储一棵树
private int[] parent;
// 记录树的「重量」
private int[] size;
// n 为图中节点的个数
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
// 将节点 p 和节点 q 连通
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 小树接到大树下面，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
// 两个连通分量合并成一个连通分量
count--;
}
// 判断节点 p 和节点 q 是否连通
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
// 返回节点 x 的连通分量根节点
private int find(int x) {
while (parent[x] != x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
// 返回图中的连通分量个数
public int count() {
return count;
}
}