克魯斯卡爾(Kruskal)算法
克魯斯卡爾(Kruskal)算法，是用來求權重連通圖的最小生成樹的算法。
基本思想：按照權值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構成回路
具體做法：首先構造一個隻含n個頂點的森林，然後依權值從小到大從連通網中選擇邊加入到森林中，并使森林中不産生回路，直至森林變成一棵樹為止
克魯斯卡爾算法在所有連接配接森林的兩個不同樹的邊裡面，尋找權值最小的邊将最小的邊加入一個不相交的集合來進行維護，每次加入時判斷該邊的起始頂點與結束頂點是否屬于同一個樹，即是否使森林産生回路，如果不産生回路則加入集合
其對應僞代碼如下：
其算法描述：
1-3 行将集合A初始化一個空集合，建立一棵樹V;
4 行 對鄰邊進行排序
5-8行 循環對邊按權重從低到高進行檢查，從每條邊的起點和終點進行檢查，判斷是否構成回路，沒有形成回路則将邊加入集合中
要點： 對邊排序；判斷是否形成回路；若沒有回路則每次選擇權值最小的邊加入集合—這裡展現了貪心算法的思想；
舉例說明
1 選取權值最小的E-F邊加入集合，E-F第一次加入肯定不會存在回路
2 選擇權值第二小的C-D邊放入集合，檢查是否形成回路
3 選取D-E加入集合
4 當選取較小的邊C-E時，發現C-D-E在集合中會形成回路，是以C-E不能加入集合
判斷回路其實也簡單：循環集合，從C-E邊的起始頂點C和終點E出發,如果形成回路則
頂點C和頂點E必然共用同一終點。
5 重複 1 2 3 4 将B-F E-G A-B加入集合，最小生成樹建構完成
代碼實作
我們使用鄰接表建構圖
class Graph<T>{
int vertexNum;
int edgeNum;
ArrayList< Edge<T>> edgesList ;
ArrayList< Vertex<T>> vertexList;
public Graph(T[] vertex){
vertexList = new ArrayList<>();
edgesList = new ArrayList<>();
this.addVertex(vertex);
}
static class Vertex<T> {
T verName;//節點存儲的内容
Edge<T> edgeLink ;//頂點的邊鍊
public Vertex(T name){
verName = name;
edgeLink = null;
}
@Override
public String toString() {
return "Vertex{" +
"verName=" + verName +
'}';
}
}
static class Edge<T> {
Vertex<T> start;//邊的頭節點
Vertex<T> end;//邊的尾部節點
int weight;//邊的權值
Edge<T> broEdge;// 節點連接配接的其他邊,指向下一個鄰接點
public Edge(Vertex<T> start, Vertex<T> end,int weight){
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"start=" + start +
", end=" + end +
", weight=" + weight +
'}';
}
}
public void addVertex(T[] vertex){
for (T c : vertex) {
vertexList.add(new Vertex<>(c));
}
vertexNum = vertex.length;
}
public void addEdge(T start,T end,int weight){
Vertex<T> startVertex = getVertex(start);
Vertex<T> endVertex = getVertex(end);
edgesList.add(concatEdge(startVertex, endVertex,weight));
concatEdge(endVertex, startVertex,weight);
edgeNum++;
}
private Edge<T> concatEdge(Vertex<T> startVertex, Vertex<T> endVertex, int weight){
Edge<T> edge = new Edge<>(startVertex,endVertex,weight);
if (startVertex.edgeLink != null){
Edge<T> broEdge = startVertex.edgeLink;
while (broEdge.broEdge != null){
broEdge = broEdge.broEdge;
}
broEdge.broEdge = edge;
}
else{
startVertex.edgeLink = edge;
}
return edge;
}
public Vertex<T> getVertex(T verName){
return vertexList.stream().filter(e -> e.verName.equals(verName)).findFirst().orElseThrow(()->new NoSuchElementException(verName+" is no present"));
}
}
求解最小生成樹
public LinkedList<Graph.Edge<Character>> kruskal(Graph<Character> graph){
ArrayList<Graph.Edge<Character>> edgesList = graph.edgesList;
edgesList.sort(Comparator.comparingInt(o -> o.weight));
LinkedList<Graph.Edge<Character>> minTree = new LinkedList<>();
int[] ends = new int[graph.edgeNum]; //用于儲存"已有最小生成樹" 中的每個頂點在最小生成樹中的終點
for (Graph.Edge<Character> edge : edgesList) {
int p1 = getIndex(graph.vertexList, edge.start);
int p2 = getIndex(graph.vertexList, edge.end);
//擷取p1這個頂點在已有最小生成樹中的終點
int m = loop(ends, p1);
//擷取p2這個頂點在已有最小生成樹中的終點
int n = loop(ends, p2);
if (m != n) {
minTree.add(edge);
ends[m] = n;//将該邊的起始頂點和終點進行連接配接，代表該邊已經在最小生成樹裡
}
}
return minTree;
}
private int loop(int[] ends, int i ) {
while (ends[i] != 0) {
i = ends[i];
}
return i;
}
private int getIndex(ArrayList<Graph.Vertex<Character>> vertexList,Graph.Vertex<Character> vertex ) {
for(int i = 0; i < vertexList.size(); i++) {
if(vertexList.get(i) == vertex) {
return i;
}
}
return -1;
}