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