【原】圖的應(yīng)用：最小生成樹

硬核項(xiàng)目經(jīng)理 2021-05-31

展開全文

圖的應(yīng)用：最小生成樹

在學(xué)習(xí)了圖的基本結(jié)構(gòu)和遍歷方式后，我們?cè)倮^續(xù)地深入學(xué)習(xí)一些圖的基本應(yīng)用。在之前的數(shù)據(jù)結(jié)構(gòu)中，我們并沒接觸太多的應(yīng)用場(chǎng)景，但是圖的這兩類應(yīng)用確是面試或考試中經(jīng)常出現(xiàn)的問題，而且出現(xiàn)的頻率還非常高，不得不來好好說一說。

什么是最小生成樹？

從前面的學(xué)習(xí)中，我們應(yīng)該能夠發(fā)現(xiàn)，圖就是一種擴(kuò)展的樹結(jié)構(gòu)。對(duì)于樹來說，它只有一個(gè)上級(jí)結(jié)點(diǎn)，同級(jí)結(jié)點(diǎn)之間沒有關(guān)聯(lián)。而圖則打破了樹的這些規(guī)則。我們?cè)俜催^來想想，能不能給定一個(gè)條件，那就是連接上所有的結(jié)點(diǎn)，但是每個(gè)結(jié)點(diǎn)之間只保留一條邊。這樣形成的一顆簡(jiǎn)單的樹其實(shí)就是能夠串聯(lián)所有結(jié)點(diǎn)的一條路徑，而最小生成樹的概念，其實(shí)就是對(duì)于有權(quán)圖來說，權(quán)數(shù)最少的那條能夠串連起所有結(jié)點(diǎn)的邊的路徑，或者也可以說是最小連通樹、最小連通子圖、最小代價(jià)樹。

從上圖中就可以看出，對(duì)于一個(gè)有權(quán)圖來，可以有許多生成樹的方式，不過不同的路線方式的結(jié)果會(huì)不同，只有最后一個(gè)路徑形成的生成樹具有路徑最小的那顆樹，就是我們需要的最小生成樹。

為什么要強(qiáng)調(diào)是有權(quán)圖呢？因?yàn)槿绻菬o權(quán)圖，所有結(jié)點(diǎn)連接起來的方案其實(shí)就沒有什么太大的意義了，因?yàn)椴还軓哪膫€(gè)結(jié)點(diǎn)出發(fā)走哪條路徑可能權(quán)值都是一樣的。而帶權(quán)路徑則總會(huì)有一條最佳的路徑是可以將所有結(jié)點(diǎn)遍歷完成并且權(quán)數(shù)還是最小的。最典型的應(yīng)用就是地圖上哪條線路成本最少呀，辦公樓布線怎么走線最經(jīng)濟(jì)之類相關(guān)的題目，基本都會(huì)牽涉到最小生成樹的概念。

關(guān)于最小生成樹的最經(jīng)典的算法，Prim 和 Kruskal 這兩個(gè)大神級(jí)別的算法是繞不過去的檻，下面我們就來粗淺地學(xué)習(xí)一下。

第一種算法 Prim

Prim 算法，中文名普里姆算法。起源就不多說了，反正是個(gè)人名，這篇文章和下篇文章中圖的應(yīng)用的這些算法名稱都是人名相關(guān)的。他們發(fā)現(xiàn)并最初使用了這些算法，然后就將這些算法以他們的名字命名了。

Prim 算法的核心思想就是：從一個(gè)結(jié)點(diǎn)出發(fā)，查看這個(gè)結(jié)點(diǎn)的所有的邊中權(quán)值最小的那條邊，然后加上這條邊所連接的那個(gè)結(jié)點(diǎn)的所有邊，再一起看哪個(gè)邊的權(quán)值最小，然后一直重復(fù)這些步驟，反正就是所有結(jié)點(diǎn)到我們出發(fā)的這個(gè)結(jié)點(diǎn)中所有權(quán)值最小的邊都看一遍，并且讓它們能夠連接所有結(jié)點(diǎn)就完成了。

看圖是不是就清晰多了。我們一步一步地看。

首先我們從第 1 個(gè)結(jié)點(diǎn)出發(fā)，然后看第 1 個(gè)結(jié)點(diǎn)相關(guān)的邊哪個(gè)權(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)連通了，所以選擇下一個(gè)最小的邊 <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)值最小的邊，這時(shí)只有 <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)值路徑，所形成的這一條路徑就是一顆最小生成樹了

從這個(gè)步驟和圖釋來說，大家可以自己嘗試寫寫這個(gè) Prim 算法的代碼，其實(shí)并不復(fù)雜。我們需要一個(gè)集合來放置已經(jīng)連通的結(jié)點(diǎn)信息，當(dāng)查找路徑的時(shí)候找到的最小權(quán)值路徑連通的結(jié)點(diǎn)不在集合中，就加入到集合中。然后不斷累加所有的路徑權(quán)值，最后就得到了遍歷整張圖的最小生成樹路徑。

// 普里姆算法
function Prim($graphArr)
{
    $n = count($graphArr);
    // 記錄 1 號(hào)頂點(diǎn)到各個(gè)頂點(diǎn)的初始距離
    $dis = [];
    for ($i = 1; $i <= $n; $i++) {
        $dis[$i] = $graphArr[1][$i];
    }

    // 將 1 號(hào)頂點(diǎn)加入生成樹
    $book[1] = 1; // 標(biāo)記一個(gè)頂點(diǎn)是否已經(jīng)加入到生成樹
    $count = 1; // 記錄生成樹中的頂點(diǎn)的個(gè)數(shù)
    $sum = 0; // 存儲(chǔ)路徑之和
    // 循環(huán)條件 生成樹中的頂點(diǎn)的個(gè)數(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)個(gè)數(shù)增加
        $sum += $dis[$j]; // 累加路徑和
        // 調(diào)整當(dāng)前頂點(diǎn) $j 的所有邊，再以 $j 為中間點(diǎn)，更新生成樹到每一個(gè)非樹頂點(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)行代碼并輸入測(cè)試數(shù)據(jù)。

php 5.4圖的應(yīng)用：最小生成樹.php
請(qǐng)輸入結(jié)點(diǎn)數(shù)：6
請(qǐng)輸入邊數(shù)：9
請(qǐng)輸入邊，格式為 出 入 權(quán)：2 4 11
請(qǐng)輸入邊，格式為 出 入 權(quán)：3 5 13
請(qǐng)輸入邊，格式為 出 入 權(quán)：4 6 3
請(qǐng)輸入邊，格式為 出 入 權(quán)：5 6 4
請(qǐng)輸入邊，格式為 出 入 權(quán)：2 3 6
請(qǐng)輸入邊，格式為 出 入 權(quán)：4 5 7
請(qǐng)輸入邊，格式為 出 入 權(quán)：1 2 1
請(qǐng)輸入邊，格式為 出 入 權(quán)：3 4 9
請(qǐng)輸入邊，格式為 出 入 權(quán)：1 3 2
19

可以看到輸出的結(jié)果和我們預(yù)期的一樣。代碼中已經(jīng)有很詳細(xì)的注釋說明了，如果直接看代碼比較暈的話，大家可以拿調(diào)試工具進(jìn)行斷點(diǎn)的單步調(diào)試來看一下具體的運(yùn)行情況。在這里我們先看一下那個(gè) dis[] 中最后都保存了什么東西。

Array
(
    [1] => 9999999
    [2] => 1
    [3] => 2
    [4] => 9
    [5] => 4
    [6] => 3
)

INFINITY 是我們定義的一個(gè)常量，在初始化 graphArr 這個(gè)鄰接矩陣時(shí)，將所有的邊都設(shè)置為 INFINITY 了，主要就是方便我們后面進(jìn)行最小值的比對(duì)。這個(gè) INFINITY 我們?cè)O(shè)置的是 9999999 這樣一個(gè)非常大的數(shù)。dis[] 中其實(shí)包含的就是結(jié)點(diǎn) 1 所經(jīng)過的每條邊所選擇的權(quán)值，把他們加起來就是我們的最終路徑長度。

第二種算法 Kruskal

Prim 算法好玩嗎？相信通過具體的算法你對(duì)最小生成樹的概念就更清晰了，不知道你會(huì)不會(huì)有個(gè)這樣的想法：直接遍歷所有的邊，給他們按權(quán)值排序，這樣我們?cè)僖来伪闅v這個(gè)排序后的邊結(jié)構(gòu)數(shù)組，然后將邊的結(jié)點(diǎn)加入到最終要生成的樹中，這樣不也能形成一個(gè)最小生成樹嘛！哇塞，你要是真的想到這個(gè)方案了那要給一個(gè)大大地贊了。這種方式就是我們最小生成樹的另一種明星算法：Kruskal 算法。它的中文名字可以叫做克魯斯卡爾算法。

看這個(gè)步驟是不是和 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ù)選擇最小的邊，此時(shí)最小的邊是 <4, 6> ，這兩個(gè)結(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)連通完畢，最小生成樹完成！

不錯(cuò)吧，又學(xué)會(huì)一個(gè)新的套路，大家也可以試試按照上面的步驟和圖釋來自己先寫寫代碼。需要注意的我們要先給所有的邊排序，才能進(jìn)行這個(gè)算法的操作。另外，每次判斷結(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)，可以直接建圖的時(shí)候使用單向圖進(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; // 存儲(chǔ)路徑之和
    for ($i = 1; $i <= count($map); $i++) {
        // 判斷一條邊的兩個(gè)頂點(diǎn)是否已經(jīng)連通，即判斷是否已在同一個(gè)集合中
        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 依然是代碼兩個(gè)結(jié)點(diǎn)，而 w 代表權(quán)重。這樣的一個(gè)可以看成是邊對(duì)象的數(shù)組就比較方便我們進(jìn)行排序了。

接著我們使用快速排序按照權(quán)值進(jìn)行排序，具體的快排算法我們?cè)诤竺鎸W(xué)習(xí)排序的時(shí)候再詳細(xì)說明，大家可以直接在文章底部復(fù)制測(cè)試代碼鏈接查看完整的代碼。

接下來就是使用并查集進(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);
    // 判斷兩個(gè)點(diǎn)是否在同一個(gè)集合中
    if ($t1 != $t2) {
        $f[$t2] = $t1;
        return true;
    }
    return false;
}

它本身還是通過遞歸的方式來將結(jié)點(diǎn)保存在一個(gè)數(shù)組中，通過判斷兩個(gè)點(diǎn)是否在同一個(gè)集合中，即兩個(gè)結(jié)點(diǎn)是否有共同的祖先來確定結(jié)點(diǎn)是否已經(jīng)加入并且連通。

關(guān)于并查集的知識(shí)本人掌握的也并不是很深入，所以這里就不班門弄斧了，大家可以自己查閱相關(guān)的資料或者深入研究各類算法書籍中的解釋。

最后運(yùn)行代碼輸出的結(jié)果和 Prim 算法的結(jié)果是一致的，都是 19 。

總結(jié)

怎么樣？最小生成樹是不是很好玩的東西，圖的結(jié)構(gòu)其實(shí)是很復(fù)雜的，不過越是復(fù)雜的東西能夠玩出的花活也越多。但是反過來說，很多公司的面試過程中關(guān)于圖的算法能考到這里的也都是大廠了，一般的小公司其實(shí)能簡(jiǎn)單地說一說深度和廣度就已經(jīng)不錯(cuò)了。我們的學(xué)習(xí)還要繼續(xù)，下一篇我們將學(xué)習(xí)的是另一個(gè)圖的廣泛應(yīng)用：最短距離。

今天的測(cè)試代碼均根據(jù) 《啊哈！算法》改寫為 PHP 形式，參考資料依然是其它各類教材。

測(cè)試代碼：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5.圖/source/5.4圖的應(yīng)用：最小生成樹.php

參考文檔：

《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越

《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研

《啊哈！算法》