【原】克魯斯卡爾算法 --- 公交站問題

貪挽懶月 2022-06-20 發(fā)布于廣東

展開全文

1. 是什么？

克魯斯卡爾算法其實(shí)也是生成最小生成樹的一種算法，和普里姆算法一樣，解決同一類問題的。

有7個(gè)公交站(A, B, C, D, E, F, G) ，現(xiàn)在需要修路把7個(gè)公交站連通，各個(gè)公交站之間的距離如下。問如何修路，能使各個(gè)公交站連通且修路的總里程數(shù)最小？

這個(gè)和上次說到的普里姆算法修路問題是一樣的，下面來看看用克魯斯卡爾算法怎么解決。

2. 算法步驟：

首先對(duì)邊的權(quán)值進(jìn)行排序，選擇權(quán)值最小的一條邊，即EF；
選擇權(quán)值第二小的邊，即CD；
選擇權(quán)值第三小的邊，即DE；
選擇權(quán)值第四小的邊，即CE，但是，如果選擇CE，那就形成回路了。什么叫回路呢？CDE這個(gè)三角形三條邊都修了路，那就是回路。所以不能選擇CE，那就嘗試選擇第五小的邊，即CF，但是CF也不能選，如果選了，四邊形CFED就形成回路了。所以繼續(xù)選擇第六小的邊，BF，這個(gè)是可以選擇的；
接下來依次選擇EG、AB。7個(gè)頂點(diǎn)總共要選擇6條邊，這6條邊分別是：EF、CD、DE、BF、EG、AB。

克魯斯卡爾算法的難點(diǎn)在于，怎么判斷選擇了這條邊是否會(huì)形成回路。

**判斷是否形成回路的方法：**記錄頂點(diǎn)在最小生成樹中的終點(diǎn)，頂點(diǎn)的終點(diǎn)是“在最小生成樹中與它連通的最大頂點(diǎn)”。然后每次需要將一條邊添加到最小生成樹時(shí)，判斷該邊的兩個(gè)頂點(diǎn)終點(diǎn)是否相同，相同就會(huì)構(gòu)成回路。

看了這段話，可能還是一臉蒙逼，還是以上面的圖為例，看步驟：

首先ABCDEFG這7個(gè)頂點(diǎn)，在頂點(diǎn)集合中應(yīng)該是按照順序存放的；
按照上面的分析，第一次選擇的是EF，毫無疑問這一條邊的終點(diǎn)是F；
第二次選擇的CD的終點(diǎn)D；
第三次選擇的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。也就是說，當(dāng)選擇了EF、CD、DE這三條邊后，C、D、E的終點(diǎn)都是F。當(dāng)然F的終點(diǎn)也是F，因?yàn)镕還沒和后面的哪個(gè)頂點(diǎn)連接。
本來接下來應(yīng)該選擇CE的，但是由于C和E的終點(diǎn)都是F，所以就會(huì)形成回路。

3. 代碼實(shí)現(xiàn)：

首先還是定義一個(gè)類，用來表示圖，如下：

/**
 * 圖
 * @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è)最小生成樹類，寫上一些基礎(chǔ)方法，比如生成圖，打印圖的鄰接矩陣等，如下：

/**
 * 最小生成樹
 * @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了，要對(duì)邊進(jìn)行排序?，F(xiàn)在邊是保存在鄰接矩陣中的，不太好處理，所以再定義一個(gè)類，用來表示邊：

/**
 * 邊的對(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è)類來表示邊，接下來就可以寫一個(gè)方法，將圖的鄰接矩陣轉(zhuǎn)成邊對(duì)象，即在MinTree類中加如下方法：

/**
* 將圖的邊，即鄰接矩陣，轉(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類中增加一個(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)備工作就做完了。接下來還需要在MinTree類中新增兩個(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)建最小生成樹
* @param graph 圖
* @param currentVertex 開始處理的頂點(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è)方法：

首先定義保存最終結(jié)果的集合；
然后定一個(gè)了一個(gè)數(shù)組，用來保存終點(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。接下來用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，也就是說，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相等，說明終點(diǎn)是同一個(gè)，都是F，所以不添加這條邊。