本文共 2210 字，大约阅读时间需要 7 分钟。

引子：

克鲁斯卡尔算法的作用是：构建图的最小生成树。

克鲁斯卡尔算法 Kruskal的构造过程：

1、初始化图：n个顶点，n个连通分量（如果两个顶点的连通分量相同，表示两点在同一个连通图中）。把所有的边（包含这个边两端的两个顶点）放入优先级队列中，按照权重从小到大。

2、选择最小权重的边，如果这个边的头顶点的和尾顶点的连通分量不同，则合并头和尾两个分量（整个连通图的点都需要修改，具体看代码）。舍弃该边。（连通分量用整数表示）

3、重复第二步，直到所有的顶点都连接着同一个连通分量里面。

package minTree;import java.util.Comparator;import java.util.Iterator;import java.util.PriorityQueue;import java.util.Queue;public class MinTree_KruskalTest {	public static void main(String[] args) {		MinTree_Kruskal m = new MinTree_Kruskal();		m.addEdge(0, 1, 6);		m.addEdge(0, 2, 1);		m.addEdge(0, 3, 5);		m.addEdge(0, 4, 10000);		m.addEdge(1, 2, 5);		m.addEdge(1, 3, 10000);		m.addEdge(1, 4, 3);		m.addEdge(1, 5, 10000);		m.addEdge(2, 3, 5);		m.addEdge(2, 4, 6);		m.addEdge(2, 5, 4);		m.addEdge(3, 4, 10000);		m.addEdge(3, 5, 2);		m.addEdge(4, 5, 6);				m.doKruskal();	}}class MinTree_Kruskal{		private Queue
   
     edges = null;		public MinTree_Kruskal(){		this.edges = new PriorityQueue<>(new MyComparator());	}		public void addEdge(int head, int tail, int weigth){		this.edges.add(new Edge(head, tail, weigth));	}	public void doKruskal(){		//优先级队列，按照权重从小到大排列		Queue
    
      tempQueue = new PriorityQueue<>(new MyComparator());		Iterator
     
       iter = edges.iterator();		//复制队列		while(iter.hasNext()){			tempQueue.add(iter.next());		}				int len = tempQueue.size();				//表示各顶点自成一个连通分量		int[] vexSet = new int[len];		for(int i = 0; i < len; i++){			vexSet[i] = i;		}				for(int i = 0; i < len; i++){			Edge e1 = null;			//队列中权重最小的边			e1 = tempQueue.poll(); 						if(e1 != null){				if(vexSet[e1.head] != vexSet[e1.tail]){					System.out.println(e1.head+" --> "+e1.tail+"; weigth = "+e1.weigth);					int t = vexSet[e1.tail];					int h = vexSet[e1.head];					//合并头和尾的连通分量					for(int j = 0; j < len; j++){						if(vexSet[j] == t){							vexSet[j] = h;						}					}				}			}		}	}			class Edge{		//头顶点		int head;		//尾顶点		int tail;		//两点的权重		int weigth;				public Edge(int head, int tail, int weigth){			this.head = head;			this.tail = tail;			this.weigth = weigth;		}	}		/**	 * 自定义比较器	 * @author LiangYH	 *	 */	class MyComparator implements Comparator
      
       {		@Override		public int compare(Edge o1, Edge o2) {			return o1.weigth - o2.weigth;		}			}}
      
     
    
   

转载地址：https://liangyihuai.blog.csdn.net/article/details/48503361 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！