在學(xué)習(xí)了圖的基本結(jié)構(gòu)和遍歷方式后，我們再繼續(xù)地深入學(xué)習(xí)一些圖的基本應(yīng)用。在之前的數(shù)據(jù)結(jié)構(gòu)中，我們并沒接觸太多的應(yīng)用場景，但是圖的這兩類應(yīng)用確是面試或考試中經(jīng)常出現(xiàn)的問題，而且出現(xiàn)的頻率還非常高，不得不來好好說一說。
什么是最小生成樹？
從前面的學(xué)習(xí)中，我們應(yīng)該能夠發(fā)現(xiàn)，圖就是一種擴(kuò)展的樹結(jié)構(gòu)。對于樹來說，它只有一個上級結(jié)點(diǎn)，同級結(jié)點(diǎn)之間沒有關(guān)聯(lián)。而圖則打破了樹的這些規(guī)則。我們再反過來想想，能不能給定一個條件，那就是連接上所有的結(jié)點(diǎn)，但是每個結(jié)點(diǎn)之間只保留一條邊。這樣形成的一顆簡單的樹其實就是能夠串聯(lián)所有結(jié)點(diǎn)的一條路徑，而最小生成樹的概念，其實就是對于有權(quán)圖來說，權(quán)數(shù)最少的那條能夠串連起所有結(jié)點(diǎn)的邊的路徑，或者也可以說是最小連通樹、最小連通子圖、最小代價樹。
從上圖中就可以看出，對于一個有權(quán)圖來，可以有許多生成樹的方式，不過不同的路線方式的結(jié)果會不同，只有最后一個路徑形成的生成樹具有路徑最小的那顆樹，就是我們需要的最小生成樹。
為什么要強(qiáng)調(diào)是有權(quán)圖呢？因為如果是無權(quán)圖，所有結(jié)點(diǎn)連接起來的方案其實就沒有什么太大的意義了，因為不管從哪個結(jié)點(diǎn)出發(fā)走哪條路徑可能權(quán)值都是一樣的。而帶權(quán)路徑則總會有一條最佳的路徑是可以將所有結(jié)點(diǎn)遍歷完成并且權(quán)數(shù)還是最小的。最典型的應(yīng)用就是地圖上哪條線路成本最少呀，辦公樓布線怎么走線最經(jīng)濟(jì)之類相關(guān)的題目，基本都會牽涉到最小生成樹的概念。
關(guān)于最小生成樹的最經(jīng)典的算法，Prim 和 Kruskal 這兩個大神級別的算法是繞不過去的檻，下面我們就來粗淺地學(xué)習(xí)一下。
第一種算法 Prim
Prim 算法，中文名 普里姆 算法。起源就不多說了，反正是個人名，這篇文章和下篇文章中圖的應(yīng)用的這些算法名稱都是人名相關(guān)的。他們發(fā)現(xiàn)并最初使用了這些算法，然后就將這些算法以他們的名字命名了。
Prim 算法的核心思想就是：從一個結(jié)點(diǎn)出發(fā)，查看這個結(jié)點(diǎn)的所有的邊中權(quán)值最小的那條邊，然后加上這條邊所連接的那個結(jié)點(diǎn)的所有邊，再一起看哪個邊的權(quán)值最小，然后一直重復(fù)這些步驟，反正就是所有結(jié)點(diǎn)到我們出發(fā)的這個結(jié)點(diǎn)中所有權(quán)值最小的邊都看一遍，并且讓它們能夠連接所有結(jié)點(diǎn)就完成了。
看圖是不是就清晰多了。我們一步一步地看。
- 首先我們從第 1 個結(jié)點(diǎn)出發(fā)，然后看第 1 個結(jié)點(diǎn)相關(guān)的邊哪個權(quán)值最小，很明顯，我們要選選擇 <1, 2> 這條邊，然后將結(jié)點(diǎn) 2 加入到選擇中
2）在結(jié)點(diǎn) 1 和結(jié)點(diǎn) 2 中選擇最權(quán)值最小的邊并連接到新的結(jié)點(diǎn)，在這里我們選擇的是 <1, 3> 這條邊，于是結(jié)點(diǎn) 3 也加入到選擇中
4）在結(jié)點(diǎn) 1、2、3 的所有邊中，選擇權(quán)值最小的邊，可以看到 <2, 3> 這條邊的權(quán)值最小，但是 2 和 3 都已經(jīng)連通了，所以選擇下一個最小的邊 <3, 4> ，結(jié)點(diǎn) 4 還沒有加入到已經(jīng)連通的結(jié)點(diǎn)中，于是就走 <3, 4> 這條邊，結(jié)點(diǎn) 4 加入已連通結(jié)點(diǎn)中
5）同樣地，在結(jié)點(diǎn) 1、2、3、4 中選擇權(quán)值最小的邊，這時只有 <4, 6> 邊是最小的，并且結(jié)點(diǎn) 6 也沒有加入到已連通結(jié)點(diǎn)中，選擇這條路線，結(jié)點(diǎn) 6 加入連通結(jié)點(diǎn)中
6）最后，在結(jié)點(diǎn) 1、2、3、4、6 中查找權(quán)值最小的邊，得到 <6, 5> 這條邊，結(jié)點(diǎn) 5 也沒連通，于是選擇這條路徑，加入結(jié)點(diǎn) 5
7）所有結(jié)點(diǎn)都已經(jīng)連通，權(quán)值累加結(jié)點(diǎn)為 19 ，當(dāng)前的這條路徑就是最小權(quán)值路徑，所形成的這一條路徑就是一顆最小生成樹了
從這個步驟和圖釋來說，大家可以自己嘗試寫寫這個 Prim 算法的代碼，其實并不復(fù)雜。我們需要一個集合來放置已經(jīng)連通的結(jié)點(diǎn)信息，當(dāng)查找路徑的時候找到的最小權(quán)值路徑連通的結(jié)點(diǎn)不在集合中，就加入到集合中。然后不斷累加所有的路徑權(quán)值，最后就得到了遍歷整張圖的最小生成樹路徑。
// 普里姆算法
function Prim($graphArr)
{
$n = count($graphArr);
// 記錄 1 號頂點(diǎn)到各個頂點(diǎn)的初始距離
$dis = [];
for ($i = 1; $i <= $n; $i++) {
$dis[$i] = $graphArr[1][$i];
}
// 將 1 號頂點(diǎn)加入生成樹
$book[1] = 1; // 標(biāo)記一個頂點(diǎn)是否已經(jīng)加入到生成樹
$count = 1; // 記錄生成樹中的頂點(diǎn)的個數(shù)
$sum = 0; // 存儲路徑之和
// 循環(huán)條件 生成樹中的頂點(diǎn)的個數(shù) 小于 總結(jié)點(diǎn)數(shù)
while ($count < $n) {
$min = INFINITY;
for ($i = 1; $i <= $n; $i++) {
// 如果當(dāng)前頂點(diǎn)沒有加入到生成樹，并且記錄中的權(quán)重比當(dāng)前權(quán)重小
if (!$book[$i] && $dis[$i] < $min) {
// 將 $min 定義為當(dāng)前權(quán)重的值
$min = $dis[$i];
$j = $i; // 用于準(zhǔn)備將頂點(diǎn)加入到生成樹記錄中
}
}
$book[$j] = 1; // 確認(rèn)將最小權(quán)重加入到生成樹記錄中
$count++; // 頂點(diǎn)個數(shù)增加
$sum += $dis[$j]; // 累加路徑和
// 調(diào)整當(dāng)前頂點(diǎn) $j 的所有邊，再以 $j 為中間點(diǎn)，更新生成樹到每一個非樹頂點(diǎn)的距離
for ($k = 1; $k <= $n; $k++) {
// 如果當(dāng)前頂點(diǎn)沒有加入到生成樹，并且記錄中的 $k 權(quán)重頂點(diǎn)大于 $j 頂點(diǎn)到 $k 頂點(diǎn)的權(quán)重
if (!$book[$k] && $dis[$k] > $graphArr[$j][$k]) {
// 將記錄中的 $k 頂點(diǎn)的權(quán)重值改為 $j 頂點(diǎn)到 $k 頂點(diǎn)的值
$dis[$k] = $graphArr[$j][$k];
}
}
}
return $sum;
}
$graphArr = [];
BuildGraph($graphArr); // 之前文章中的生成鄰接矩陣的函數(shù)
echo Prim($graphArr); // 19
我們運(yùn)行代碼并輸入測試數(shù)據(jù)。
php 5.4圖的應(yīng)用：最小生成樹.php
請輸入結(jié)點(diǎn)數(shù)：6
請輸入邊數(shù)：9
請輸入邊，格式為 出 入 權(quán)：2 4 11
請輸入邊，格式為 出 入 權(quán)：3 5 13
請輸入邊，格式為 出 入 權(quán)：4 6 3
請輸入邊，格式為 出 入 權(quán)：5 6 4
請輸入邊，格式為 出 入 權(quán)：2 3 6
請輸入邊，格式為 出 入 權(quán)：4 5 7
請輸入邊，格式為 出 入 權(quán)：1 2 1
請輸入邊，格式為 出 入 權(quán)：3 4 9
請輸入邊，格式為 出 入 權(quán)：1 3 2
19
可以看到輸出的結(jié)果和我們預(yù)期的一樣。代碼中已經(jīng)有很詳細(xì)的注釋說明了，如果直接看代碼比較暈的話，大家可以拿調(diào)試工具進(jìn)行斷點(diǎn)的單步調(diào)試來看一下具體的運(yùn)行情況。在這里我們先看一下那個 dis[] 中最后都保存了什么東西。
Array
(
[1] => 9999999
[2] => 1
[3] => 2
[4] => 9
[5] => 4
[6] => 3
)
INFINITY 是我們定義的一個常量，在初始化 graphArr 這個鄰接矩陣時，將所有的邊都設(shè)置為 INFINITY 了，主要就是方便我們后面進(jìn)行最小值的比對。這個 INFINITY 我們設(shè)置的是 9999999 這樣一個非常大的數(shù)。dis[] 中其實包含的就是結(jié)點(diǎn) 1 所經(jīng)過的每條邊所選擇的權(quán)值，把他們加起來就是我們的最終路徑長度。
第二種算法 Kruskal
Prim 算法好玩嗎？相信通過具體的算法你對最小生成樹的概念就更清晰了，不知道你會不會有個這樣的想法：直接遍歷所有的邊，給他們按權(quán)值排序，這樣我們再依次遍歷這個排序后的邊結(jié)構(gòu)數(shù)組，然后將邊的結(jié)點(diǎn)加入到最終要生成的樹中，這樣不也能形成一個最小生成樹嘛！哇塞，你要是真的想到這個方案了那要給一個大大地贊了。這種方式就是我們最小生成樹的另一種明星算法：Kruskal 算法。它的中文名字可以叫做 克魯斯卡爾 算法。
看這個步驟是不是和 Prim 就完全不一樣了？不急，我們還是一步一步地來看。
1）在所有的邊中，選擇最小的那條邊，也就是 <1, 2> 這條邊，結(jié)點(diǎn) 1 和結(jié)點(diǎn) 2 連通
2）接著選擇第二小的邊，<1, 3> 邊符合條件，并且結(jié)點(diǎn) 3 沒有連通，加入結(jié)點(diǎn) 3
3）繼續(xù)選擇最小的邊，此時最小的邊是 <4, 6> ，這兩個結(jié)點(diǎn)都沒有連通，直接加入
5）接下來是 <6, 5> 這條邊最小，繼續(xù)連通并將結(jié)點(diǎn) 5 加入
6）好了，左右兩邊成型了，現(xiàn)在最小的邊是 <2, 3> 邊，不過結(jié)點(diǎn) 2 和結(jié)點(diǎn) 3 已經(jīng)連通了，放棄！選擇 <4, 5> 邊，同樣，結(jié)點(diǎn)4 和結(jié)點(diǎn) 5 也已經(jīng)連通了，放棄！選擇 <3, 4> 邊，OK，這兩條邊還沒有連通，直接連通，所有結(jié)點(diǎn)連通完畢，最小生成樹完成！
不錯吧，又學(xué)會一個新的套路，大家也可以試試按照上面的步驟和圖釋來自己先寫寫代碼。需要注意的我們要先給所有的邊排序，才能進(jìn)行這個算法的操作。另外，每次判斷結(jié)點(diǎn)連通也是一件費(fèi)事的工作，使用深度優(yōu)先或者廣度優(yōu)先遍歷是沒問題的，但效率太低，讓我們看看大神（算法書中）們是怎么做的。
// 克魯斯卡爾算法
function Kruskal($graphArr)
{
global $map, $f;
$hasMap = [];
$i = 1;
// 轉(zhuǎn)換為序列形式方便排序
// O(mn)或O(n^2)，可以直接建圖的時候使用單向圖進(jìn)行建立就不需要這一步了
foreach ($graphArr as $x => $v) {
foreach ($v as $y => $vv) {
if ($vv == INFINITY) {
continue;
}
if (!isset($hasMap[$x][$y]) && !isset($hasMap[$y][$x])) {
$map[$i] = [
'x' => $x,
'y' => $y,
'w' => $vv,
];
$hasMap[$x][$y] = 1;
$hasMap[$y][$x] = 1;
$i++;
}
}
}
// 使用快排按照權(quán)重排序
quicksort(1, count($map));
// 初始化并查集
for ($i = 1; $i <= count($graphArr); $i++) {
$f[$i] = $i;
}
$count = 0; // 已記錄結(jié)點(diǎn)數(shù)量
$sum = 0; // 存儲路徑之和
for ($i = 1; $i <= count($map); $i++) {
// 判斷一條邊的兩個頂點(diǎn)是否已經(jīng)連通，即判斷是否已在同一個集合中
if (merge($map[$i]['x'], $map[$i]['y'])) { // 如果目前已連通，則選用這條邊
$count++;
$sum += $map[$i]['w'];
}
if ($count == count($map) - 1) { // 直到選了n-1條邊后退出
break;
}
}
return $sum;
}
Oh my God！代碼多了好多，還有好多莫名其妙的東西出現(xiàn)了。在上文中說過，我們要使用 Kruskal 算法就得先給邊排序。所以我們先將鄰接矩陣轉(zhuǎn)換成 map[x,y,w] 的形式，x 和 y 依然是代碼兩個結(jié)點(diǎn)，而 w 代表權(quán)重。這樣的一個可以看成是邊對象的數(shù)組就比較方便我們進(jìn)行排序了。
接著我們使用快速排序按照權(quán)值進(jìn)行排序，具體的快排算法我們在后面學(xué)習(xí)排序的時候再詳細(xì)說明，大家可以直接在文章底部復(fù)制測試代碼鏈接查看完整的代碼。
接下來就是使用并查集進(jìn)行 Kruskal 算法的操作了。并查集就是代替深度和廣度優(yōu)先遍歷來快速確定結(jié)點(diǎn)連通情況的一套算法。
$f = [];
// 并查集尋找祖先的函數(shù)
function getf($v)
{
global $f;
if ($f[$v] == $v) {
return $v;
} else {
// 路徑壓縮
$f[$v] = getf($f[$v]);
return $f[$v];
}
}
// 并查集合并兩子集合的函數(shù)
function merge($v, $u)
{
global $f;
$t1 = getf($v);
$t2 = getf($u);
// 判斷兩個點(diǎn)是否在同一個集合中
if ($t1 != $t2) {
$f[$t2] = $t1;
return true;
}
return false;
}
它本身還是通過遞歸的方式來將結(jié)點(diǎn)保存在一個數(shù)組中，通過判斷兩個點(diǎn)是否在同一個集合中，即兩個結(jié)點(diǎn)是否有共同的祖先來確定結(jié)點(diǎn)是否已經(jīng)加入并且連通。
關(guān)于并查集的知識本人掌握的也并不是很深入，所以這里就不班門弄斧了，大家可以自己查閱相關(guān)的資料或者深入研究各類算法書籍中的解釋。
最后運(yùn)行代碼輸出的結(jié)果和 Prim 算法的結(jié)果是一致的，都是 19 。
總結(jié)
怎么樣？最小生成樹是不是很好玩的東西，圖的結(jié)構(gòu)其實是很復(fù)雜的，不過越是復(fù)雜的東西能夠玩出的花活也越多。但是反過來說，很多公司的面試過程中關(guān)于圖的算法能考到這里的也都是大廠了，一般的小公司其實能簡單地說一說深度和廣度就已經(jīng)不錯了。我們的學(xué)習(xí)還要繼續(xù)，下一篇我們將學(xué)習(xí)的是另一個圖的廣泛應(yīng)用：最短距離。
今天的測試代碼均根據(jù) 《啊哈！算法》 改寫為 PHP 形式，參考資料依然是其它各類教材。
測試代碼：
參考文檔：
《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏
《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越
《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研
《啊哈！算法》
