「一、是什么？」
「1. 應(yīng)用場(chǎng)景：」
有7個(gè)村莊(A, B, C, D, E, F, G) ，現(xiàn)在需要修路把7個(gè)村莊連通，各個(gè)村莊之間的距離如下。問(wèn)如何修路，能使各個(gè)村莊連通且修路的總里程數(shù)最??？
修路問(wèn)題這就是經(jīng)典的修路問(wèn)題，就可以用普里姆算法來(lái)解決。
「2.最小生成樹(shù)：」
要使總里程數(shù)最小，那么就要盡可能修少路，并且修的每條路距離應(yīng)該小，這樣加起來(lái)的總里程數(shù)才會(huì)少。這就是求**最小生成樹(shù)(MST)**的過(guò)程。關(guān)于最小生成樹(shù)，介紹如下：
給定一個(gè)帶權(quán)的無(wú)向連通圖,如何選取一棵生成樹(shù),使樹(shù)上所有邊上權(quán)的總和為最小,這叫最小生成樹(shù) ；
什么意思呢？下面是一個(gè)圖和它對(duì)應(yīng)的生成樹(shù)：
生成樹(shù)這是這個(gè)圖對(duì)應(yīng)的其中三種生成樹(shù)，每條邊有權(quán)值，權(quán)值加起來(lái)最小的那棵樹(shù)，就叫做最小生成樹(shù)。求最小生成樹(shù)，可以用「普里姆算法」和「克魯斯卡爾算法」。
「二、普里姆算法步驟：」
修路問(wèn)題還是以這個(gè)圖為例，普里姆算法過(guò)程如下：
創(chuàng)建一個(gè)集合，保存選擇的頂點(diǎn)。首先選取頂點(diǎn)A，表示從A開(kāi)始處理，將A加入到集合中。與A直接連通的有C、B、G，其中AG的權(quán)值最小，所以選擇的是G，G加入到集合中。
現(xiàn)在集合中有A和G，和A直接誒連通且還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)有C、B，和G直接連通且還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)有E、B、F。其中權(quán)值最小的是GB，所以選擇B，B加入到集合。
現(xiàn)在集合中有A、G、B。和A直接連通且沒(méi)訪問(wèn)過(guò)的有C，和G直接連通且沒(méi)訪問(wèn)過(guò)的是E、F，和B直接連通且沒(méi)訪問(wèn)過(guò)的是D。其中權(quán)值最小的GE，所以選擇E，E加入到集合。
……
- 按照上面的方法，直到所有村莊都加到了集合中。最后選擇的是AGBEFDC。
「三、代碼實(shí)現(xiàn)：」
要用代碼實(shí)現(xiàn)上述過(guò)程，首先我們要用鄰接矩陣將這個(gè)圖構(gòu)建出來(lái)。首先創(chuàng)建一個(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;
}
}
然后，創(chuàng)建一個(gè)最小生成樹(shù)類：
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]));
}
}
}
現(xiàn)在，就要在最小生成樹(shù)類中用普里姆算法創(chuàng)建最小生成樹(shù)，在MinTree類中加一個(gè)方法，如下：
/**
* 普里姆算法創(chuàng)建最小生成樹(shù)
* @param graph 圖
* @param currentVertex 開(kāi)始處理的頂點(diǎn)
*/
public Map<String, Integer> prim(Graph graph, String currentVertex) {
Map<String, Integer> resultMap = new HashMap<>(); // 保存結(jié)果的集合，key是兩個(gè)頂點(diǎn)，value是這兩個(gè)頂點(diǎn)邊的長(zhǎng)度
List<String> vertexs = graph.vertexs; // 圖的頂點(diǎn)
int vertexCount = vertexs.size(); // 頂點(diǎn)的個(gè)數(shù)
int currentVertexIndex = vertexs.indexOf(currentVertex); // 當(dāng)前處理頂點(diǎn)的索引
boolean[] isVisited = new boolean[vertexCount]; // 頂點(diǎn)是否被訪問(wèn)過(guò)
isVisited[currentVertexIndex] = true; // 標(biāo)記當(dāng)前處理的頂點(diǎn)為已訪問(wèn)
int num = 10000; // 初始化一個(gè)較大的數(shù)，用來(lái)比較權(quán)值的
int index1 = -1; // 記錄找到的兩個(gè)頂點(diǎn)的索引
int index2 = -1; // 記錄找到的兩個(gè)頂點(diǎn)的索引
// n個(gè)頂點(diǎn)要生成n-1條邊，所以循環(huán)n-1次
for (int times=0; times<vertexCount-1; times++) {
for (int i=0; i<vertexCount; i++) { // i表示訪問(wèn)過(guò)的頂點(diǎn)
for (int j=0; j<vertexCount; j++) { // j表示未訪問(wèn)過(guò)的頂點(diǎn)
if (isVisited[i] && !isVisited[j] && graph.edges[i][j] < num) {
num = graph.edges[i][j];
index1 = i;
index2 = j;
}
}
}
resultMap.put("<" + vertexs.get(index1) + "," + vertexs.get(index2) + ">", num);
isVisited[index2] = true;
// 重置num
num = 10000;
}
return resultMap;
}
關(guān)于這個(gè)方法也很好理解，也有詳細(xì)的注釋。下面就可以寫個(gè)測(cè)試方法，將案例中的圖構(gòu)建出來(lái)，求出修路的方案：
public static void main(String[] args) {
List<String> vertexs = new ArrayList<>();
vertexs.add("A");
vertexs.add("B");
vertexs.add("C");
vertexs.add("D");
vertexs.add("E");
vertexs.add("F");
vertexs.add("G");
int[][] edges = new int[][] {
// 100表示沒(méi)有連通
//A B C D E F G
{100, 5, 7, 100, 100, 100, 2}, // A
{ 5, 100, 100, 9, 100, 100, 3}, // B
{ 7, 100, 100, 100, 8, 100, 100},// C
{100, 9, 100, 100, 100, 4, 100},// D
{100, 100, 8, 100, 100, 5, 4}, // E
{100, 100, 100, 4, 5, 100, 6}, // F
{ 2, 3, 100, 100, 4, 6, 100} // G
};
MinTree minTree = new MinTree();
Graph graph = minTree.createGraph(vertexs, edges);
Map<String, Integer> resultMap = minTree.prim(graph, "A");
for (String key : resultMap.keySet()) {
System.out.println(key + ": " + resultMap.get(key));
}
}
最后的結(jié)果是：
修路方案
