1. 是什么？
克魯斯卡爾算法其實(shí)也是生成最小生成樹(shù)的一種算法，和普里姆算法一樣，解決同一類(lèi)問(wèn)題的。
有7個(gè)公交站(A, B, C, D, E, F, G) ，現(xiàn)在需要修路把7個(gè)公交站連通，各個(gè)公交站之間的距離如下。問(wèn)如何修路，能使各個(gè)公交站連通且修路的總里程數(shù)最??？
公交站問(wèn)題這個(gè)和上次說(shuō)到的普里姆算法修路問(wèn)題是一樣的，下面來(lái)看看用克魯斯卡爾算法怎么解決。
2. 算法步驟：
首先對(duì)邊的權(quán)值進(jìn)行排序，選擇權(quán)值最小的一條邊，即EF；
選擇權(quán)值第四小的邊，即CE，但是，如果選擇CE，那就形成回路了。什么叫回路呢？CDE這個(gè)三角形三條邊都修了路，那就是回路。所以不能選擇CE，那就嘗試選擇第五小的邊，即CF，但是CF也不能選，如果選了，四邊形CFED就形成回路了。所以繼續(xù)選擇第六小的邊，BF，這個(gè)是可以選擇的；
接下來(lái)依次選擇EG、AB。7個(gè)頂點(diǎn)總共要選擇6條邊，這6條邊分別是：EF、CD、DE、BF、EG、AB。
克魯斯卡爾算法的難點(diǎn)在于，怎么判斷選擇了這條邊是否會(huì)形成回路。
- **判斷是否形成回路的方法：**記錄頂點(diǎn)在最小生成樹(shù)中的終點(diǎn)，頂點(diǎn)的終點(diǎn)是“在最小生成樹(shù)中與它連通的最大頂點(diǎn)”。然后每次需要將一條邊添加到最小生成樹(shù)時(shí)，判斷該邊的兩個(gè)頂點(diǎn)終點(diǎn)是否相同，相同就會(huì)構(gòu)成回路。
看了這段話，可能還是一臉蒙逼，還是以上面的圖為例，看步驟：
首先ABCDEFG這7個(gè)頂點(diǎn)，在頂點(diǎn)集合中應(yīng)該是按照順序存放的；
按照上面的分析，第一次選擇的是EF，毫無(wú)疑問(wèn)這一條邊的終點(diǎn)是F；
第三次選擇的DE，終點(diǎn)是F，因?yàn)榇藭r(shí)D和E相連，D又和F相連，所以D的終點(diǎn)是F。而且，因?yàn)镃和D是相連的，D和E相連，E和F也是相連的，所以C的終點(diǎn)此時(shí)變成了F。也就是說(shuō)，當(dāng)選擇了EF、CD、DE這三條邊后，C、D、E的終點(diǎn)都是F。當(dāng)然F的終點(diǎn)也是F，因?yàn)镕還沒(méi)和后面的哪個(gè)頂點(diǎn)連接。
本來(lái)接下來(lái)應(yīng)該選擇CE的，但是由于C和E的終點(diǎn)都是F，所以就會(huì)形成回路。
3. 代碼實(shí)現(xiàn)：
首先還是定義一個(gè)類(lèi)，用來(lái)表示圖，如下：
/**
* 圖
* @author zhu
*
*/
class Graph{
List<String> vertexs; // 存放頂點(diǎn)
int[][] edges; // 鄰接矩陣，存放邊
public Graph(List<String> vertexs, int[][] edges) {
this.vertexs = vertexs;
this.edges = edges;
}
}
然后，再定義一個(gè)最小生成樹(shù)類(lèi)，寫(xiě)上一些基礎(chǔ)方法，比如生成圖，打印圖的鄰接矩陣等，如下：
/**
* 最小生成樹(shù)
* @author zhu
*
*/
class MinTree{
/**
* 創(chuàng)建圖
* @param vertex 頂點(diǎn)集合
* @param edges 鄰接矩陣
*/
public Graph createGraph(List<String> vertex, int[][] edges) {
return new Graph(vertex, edges);
}
/**
* 打印圖的二維數(shù)組
* @param graph
*/
public void printGraph(Graph graph) {
int[][] edges = graph.edges;
for (int i=0; i<edges.length; i++) {
System.out.println(Arrays.toString(edges[i]));
}
}
}
因?yàn)槲覀兩厦娴姆治稣f(shuō)了，要對(duì)邊進(jìn)行排序。現(xiàn)在邊是保存在鄰接矩陣中的，不太好處理，所以再定義一個(gè)類(lèi)，用來(lái)表示邊：
/**
* 邊的對(duì)象
* @author zhu
*
*/
class EdgeObject{
String start; // 邊的端點(diǎn)
String end; // 邊的另一個(gè)端點(diǎn)
int weight; // 邊的權(quán)值
public EdgeObject(String start, String end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public String toString() {
return "EdgeObject [start=" + start + ", end=" + end + ", weight=" + weight + "]";
}
}
有了這個(gè)類(lèi)來(lái)表示邊，接下來(lái)就可以寫(xiě)一個(gè)方法，將圖的鄰接矩陣轉(zhuǎn)成邊對(duì)象，即在MinTree類(lèi)中加如下方法：
/**
* 將圖的邊，即鄰接矩陣，轉(zhuǎn)成邊對(duì)象
* @param graph
* @return
*/
public List<EdgeObject> transfer2Object(Graph graph){
List<EdgeObject> edgeList = new ArrayList<>();
for (int i=0; i<graph.edges.length; i++) {
for (int j=i+1; j<graph.edges[0].length; j++) {
if (graph.edges[i][j] != 100) {
EdgeObject edgeObject = new EdgeObject(graph.vertexs.get(i), graph.vertexs.get(j), graph.edges[i][j]);
edgeList.add(edgeObject);
}
}
}
return edgeList;
}
獲取到了邊對(duì)象的集合，就可以對(duì)其進(jìn)行排序了，所以在MinTree類(lèi)中增加一個(gè)排序的方法：
/**
* 對(duì)邊進(jìn)行排序
* @param edgeObject
*/
public void sortEdges(List<EdgeObject> edgeObjects) {
Collections.sort(edgeObjects, new Comparator<EdgeObject>() {
@Override
public int compare(EdgeObject o1, EdgeObject o2) {
return o1.weight - o2.weight;
}
});
}
至此，對(duì)邊進(jìn)行排序的準(zhǔn)備工作就做完了。接下來(lái)還需要在MinTree類(lèi)中新增兩個(gè)方法，即實(shí)現(xiàn)克魯斯卡爾算法的方法，如下：
/**
* 獲取索引為i的頂點(diǎn)的終點(diǎn)
* @param endArray 存放終點(diǎn)的數(shù)組
* @param i 傳入頂點(diǎn)的索引
* @return 頂點(diǎn)i的終點(diǎn)對(duì)應(yīng)的索引
*/
public int getEnd(int[] endArray, int i) {
while (endArray[i] != 0) {
i = endArray[i];
}
return i;
}
/**
* 克魯斯卡爾算法創(chuàng)建最小生成樹(shù)
* @param graph 圖
* @param currentVertex 開(kāi)始處理的頂點(diǎn)
*/
public List<EdgeObject> kruskal(Graph graph) {
// 最終選擇的邊的集合
List<EdgeObject> resultList = new ArrayList<>();
// 用于保存終點(diǎn)的數(shù)組
int[] ends = new int[graph.vertexs.size()];
// 將圖的鄰接矩陣轉(zhuǎn)成邊對(duì)象集合
List<EdgeObject> list = transfer2Object(graph);
// 對(duì)邊進(jìn)行排序
sortEdges(list);
// 遍歷邊的集合
for (EdgeObject e : list) {
int p1 = graph.vertexs.indexOf(e.start); // 邊的第一個(gè)頂點(diǎn)的索引
int p2 = graph.vertexs.indexOf(e.end); // 邊的第二個(gè)頂點(diǎn)的索引
int m = getEnd(ends, p1); // 獲取p1的終點(diǎn)
int n = getEnd(ends, p2); // 獲取p2的終點(diǎn)
if (m != n) { // 如果這兩個(gè)頂點(diǎn)的終點(diǎn)相同，就會(huì)構(gòu)成回路，反之就可以添加這條邊
ends[m] = n; // 將索引為m的頂點(diǎn)的終點(diǎn)設(shè)置為索引為n的頂點(diǎn)
resultList.add(e); // 將這條邊加入到保存結(jié)果的集合中
}
}
return resultList;
}
解釋一下這兩個(gè)方法，首先看第二個(gè)方法：
然后定一個(gè)了一個(gè)數(shù)組，用來(lái)保存終點(diǎn)。數(shù)組的大小就是圖的頂點(diǎn)的個(gè)數(shù)。下標(biāo)表示的是頂點(diǎn)，比如下標(biāo)0，那代表的就是A這個(gè)頂點(diǎn)，下標(biāo)1代表的就是B這個(gè)頂點(diǎn)；下標(biāo)對(duì)應(yīng)的值表示的是該下標(biāo)對(duì)應(yīng)的頂點(diǎn)的終點(diǎn)的索引。比如ends[0] = 1，表示的是A的終點(diǎn)是B。
再然后調(diào)用上面的方法，將鄰接矩陣轉(zhuǎn)成邊對(duì)象的集合，并且進(jìn)行排序；
接著遍歷這個(gè)邊的集合，每拿到一條邊，就判斷這條邊的兩個(gè)端點(diǎn)的終點(diǎn)是否相同。比如第一次拿到的邊是EF，那么p1 = 4, p2 = 5。接下來(lái)用getEnd方法去獲取終點(diǎn)。獲取p1終點(diǎn)的時(shí)候，保存終點(diǎn)的ends數(shù)組中還全部都是0，所以ends[p1] = 0，不進(jìn)入while循環(huán)，直接return了p1的值，即m = 4；同理n = 5。m不等于n，這時(shí)，就讓ends[4] = 5，4對(duì)應(yīng)的是E，5對(duì)應(yīng)的是F，這句話的作用就是將E的終點(diǎn)設(shè)置為了F。
拿到的第二條邊應(yīng)該是CD，p1 = 2, p2 = 3，m = 2, n = 3，ends[2] = 3，將C的終點(diǎn)設(shè)置成了D。
拿到的第三條邊是DE，p1 = 3, p2 = 4，因?yàn)?code style="font-size: 14px;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(0, 150, 136);">ends[3]、ends[4] = 0，不會(huì)進(jìn)入while循環(huán)，所以m = 3, n = 4，ends[3] = 4，將D的終點(diǎn)設(shè)置成了E。
拿到的第四條邊是CE，p1 = 2, p2 = 4，此時(shí)，ends[2] = 3 != 0，所以進(jìn)入while循環(huán)，ends[3] = 4 != 0, ends[4] = 5 != 0, ends[5] = 0，所以m = 5，也就是說(shuō)，C的終點(diǎn)是索引5對(duì)應(yīng)的，即F；接著看n等于多少。ends[4] = 5 != 0，進(jìn)入while循環(huán)，ends[5] = 0，所以n = 5，此時(shí)m和n相等，說(shuō)明終點(diǎn)是同一個(gè)，都是F，所以不添加這條邊。
……
這里就是getEnd這個(gè)方法不太好理解，調(diào)試一下就很清晰了。
