總目錄：地址如下看總綱
1、應(yīng)用場(chǎng)景-修路問題
（1）有勝利鄉(xiāng)有7個(gè)村莊(A, B, C, D, E, F, G) ，現(xiàn)在需要修路把7個(gè)村莊連通
（2）各個(gè)村莊的距離用邊線表示(權(quán)) ，比如 A – B 距離 5公里
（3）問：如何修路保證各個(gè)村莊都能連通，并且總的修建公路總里程最短?
常規(guī)思路: 將10條邊，連接即可，但是總的里程數(shù)不是最小
正確思路：盡可能的選擇少的路線，并且每條路線最小，保證總里程數(shù)最少
2、最小生成樹
修路問題本質(zhì)就是就是最小生成樹問題， 最小生成樹(Minimum Cost Spanning Tree)，簡(jiǎn)稱MST
（1）給定一個(gè)帶權(quán)的無向連通圖,如何選取一棵生成樹,使樹上所有邊上權(quán)的總和為最小,這叫最小生成樹
（2）N個(gè)頂點(diǎn)，一定有N-1條邊
（3）包含全部頂點(diǎn)
（4）N-1條邊都在圖中
（5）求最小生成樹的算法主要是普里姆?算法和克魯斯卡爾算法
3、普利姆算法
（1）普利姆(Prim)算法求最小生成樹，也就是在包含n個(gè)頂點(diǎn)的連通圖中，找出只有(n-1)條邊包含所有n個(gè)頂點(diǎn)的連通子圖，也就是所謂的極小連通子圖
（2）文字思路：看不懂也無所謂，概述而已，詳細(xì)看圖解
①設(shè)G=(V,E)是連通網(wǎng)，T=(U,D)是最小生成樹，V,U是頂點(diǎn)集合，E,D是邊的集合
②若從頂點(diǎn)u開始構(gòu)造最小生成樹，則從集合V中取出頂點(diǎn)u放入集合U中，標(biāo)記頂點(diǎn)v的visited[u]=1（既被訪問過了）
③若集合U中頂點(diǎn)ui與集合V-U中的頂點(diǎn)vj之間存在邊，則尋找這些邊中權(quán)值最小的邊，但不能構(gòu)成回路，將頂點(diǎn)vj加入集合U中，將邊（ui,vj）加入集合D中，標(biāo)記visited[vj]=1
④重復(fù)步驟②，直到U與V相等，即所有頂點(diǎn)都被標(biāo)記為訪問過，此時(shí)D中有n-1條邊
（3）圖解思路：清晰一些，關(guān)于理解
4、代碼
public class PrimAlgorithm {
public static void main(String[] args) {
// 測(cè)試圖創(chuàng)建
char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
int verxs = data.length;
//鄰接矩陣的關(guān)系使用二維數(shù)組表示,10000這個(gè)大數(shù)，表示兩個(gè)點(diǎn)不聯(lián)通
int[][] weight = new int[][]{
{10000, 5, 7, 10000, 10000, 10000, 2},
{5, 10000, 10000, 9, 10000, 10000, 3},
{7, 10000, 10000, 10000, 8, 10000, 10000},
{10000, 9, 10000, 10000, 10000, 4, 10000},
{10000, 10000, 8, 10000, 10000, 5, 4},
{10000, 10000, 10000, 4, 5, 10000, 6},
{2, 3, 10000, 10000, 4, 6, 10000},};
//創(chuàng)建MGraph對(duì)象
MGraph graph = new MGraph (verxs);
//創(chuàng)建一個(gè)MinTree對(duì)象
MinTree minTree = new MinTree ( );
minTree.createGraph (graph, verxs, data, weight);
//輸出
minTree.showGraph (graph);
//測(cè)試普利姆算法
minTree.prim (graph, 0);
}
}
// 構(gòu)建最小生成樹對(duì)象 --- 村莊圖
class MinTree {
/**
* 構(gòu)建圖的鄰接矩陣(初始化)
*
* @param graph 圖對(duì)象
* @param verxs 圖對(duì)應(yīng)的頂點(diǎn)個(gè)數(shù)
* @param data 圖的各個(gè)頂點(diǎn)編號(hào)，這里不是權(quán)值（編號(hào)作為表示，不用于計(jì)算；權(quán)值通常用于計(jì)算，個(gè)人理解--阿K）
* @param weight 圖的鄰接矩陣
*/
public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight) {
for (int i = 0; i < verxs; i++) {// 遍歷各個(gè)頂點(diǎn)
graph.data[i] = data[i];
for (int j = 0; j < verxs; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
// 顯示圖的鄰接矩陣
public void showGraph(MGraph graph) {
for (int[] link : graph.weight) {
System.out.println (Arrays.toString (link));
}
}
/**
* @param graph 圖
* @param v 表示從圖的第幾個(gè)頂點(diǎn)開始生成 'A'-0,'B'-1 ...
*/
public void prim(MGraph graph, int v) {
// visited[] 標(biāo)記節(jié)點(diǎn)(頂點(diǎn))是否被訪問過
int[] visited = new int[graph.verxs];
// 初始化，默認(rèn) 0 是未訪問過，可以不寫，但是我愿意！
for (int i = 0; i < visited.length; i++) {
visited[i] = 0;
}
// 把當(dāng)前節(jié)點(diǎn)標(biāo)記為已訪問過
visited[v] = 1;
// h1 and h2 record double node of subscript(鄰接矩陣是二位數(shù)組，對(duì)應(yīng)著 double subscript)
int h1 = -1;
int h2 = -1;
// 將 minWeight 初始化成大數(shù) 10000，后面遍歷過程中會(huì)被替換（為什么初始化成大數(shù)，因?yàn)檫@樣默認(rèn)是走不通的 根據(jù)案例設(shè)計(jì)）
int minWeight = 10000;// 邊（最小權(quán)值）
// 核心部分：
for (int k = 1; k < graph.verxs; k++) {// 公式中 頂點(diǎn)個(gè)數(shù)為n ，邊為 n-1，所以 從 1開始
// 該雙層循環(huán)作用：用于確定每一次生成的子圖，和哪個(gè)節(jié)點(diǎn)的距離最近
// 子圖：就是圖解上的步驟 1 - 6 中， 1 是 A-C [7]， A-G[2] ，A-B[5] ， 2 是 A-C[7] ，A-B[5] ， G-B[3] ，G-E[4] ，G-F[6] ......
// 其實(shí)就是對(duì)圖遍歷兩遍，一遍訪問過的，一遍沒訪問過的，有訪問過的根據(jù)沒訪問過的計(jì)算權(quán)值(邊)，得出最小，然后標(biāo)記為已經(jīng)訪問過，繼續(xù)循環(huán) k 層
for (int i = 0; i < graph.verxs; i++) {// i 索引對(duì)應(yīng)的節(jié)點(diǎn)表示 被訪問過的節(jié)點(diǎn)，標(biāo)識(shí)為 0
for (int j = 0; j < graph.verxs; j++) {// j 索引對(duì)應(yīng)的節(jié)點(diǎn)表示 未被訪問過的節(jié)點(diǎn)，標(biāo)識(shí)為 1
if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {// 當(dāng)前節(jié)點(diǎn)的權(quán)值(邊)小于最小節(jié)點(diǎn)的權(quán)值（邊）
// 替換 minWeight(尋找已經(jīng)訪問過的結(jié)點(diǎn)和未訪問過的結(jié)點(diǎn)間的權(quán)值最小的邊)
minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
// 找到了一條邊，是最小的
System.out.println ("邊<" + graph.data[h1] + "," + graph.data[h2] + "> 權(quán)值:" + minWeight);
// 將當(dāng)前節(jié)點(diǎn)標(biāo)記為已經(jīng)訪問
visited[h2] = 1;// 為什么 h1 不用置為已經(jīng)標(biāo)記？ 因?yàn)閔1 本身已經(jīng)是標(biāo)記好的用來篩選，所以沒必要
// 重新設(shè)置為最大值
minWeight = 10000;
}
}
}
// 圖對(duì)象
class MGraph {
int verxs; // 表示圖中節(jié)點(diǎn)的個(gè)數(shù)
char[] data; // 存放節(jié)點(diǎn)的數(shù)據(jù)
int[][] weight;// 存放邊（既 鄰接矩陣）
public MGraph(int verxs) {
this.verxs = verxs;
data = new char[verxs];
weight = new int[verxs][verxs];
}
}
5、倉(cāng)庫(kù)坐標(biāo)
