PHP中的最小生成樹演算法詳解

PHP中的最小生成樹演算法詳解

最小生成樹（Minimum Spanning Tree，簡稱MST）是圖論中的重要概念，用來解決連通圖最小權重邊的選擇問題。在PHP語言中，我們可以透過一些經典的最小生成樹演算法來實現這個功能。本文將詳細介紹兩種常用的最小生成樹演算法：Prim演算法和Kruskal演算法，並給出對應的PHP程式碼範例。

一、Prim演算法

Prim演算法是一種貪心演算法，它從一個頂點開始，逐步擴展產生最小生成樹。具體過程如下：

1. 選擇起始頂點，將其加入已選取的集合。
2. 從與目前已選取的頂點集合相鄰的頂點中，選擇權重最小的邊，並加入已選取的邊集合。
3. 將該邊所連接的頂點也加入已選取的頂點集合。
4. 重複步驟2和3，直到所有的頂點都加入已選取的集合。
5. 最終得到的邊集合就是最小生成樹。

以下是用PHP實作Prim演算法的程式碼範例：

function prim($graph) {
    $numVertices = count($graph);
    $selected = array_fill(0, $numVertices, false); // 记录已选择的顶点
    $parent = array_fill(0, $numVertices, -1); // 记录最小生成树的父节点

    $selected[0] = true; // 从第一个顶点开始
    $minWeight = 0;

    for ($i = 0; $i < $numVertices - 1; $i++) {
        $minKey = -1;
        $minVal = PHP_INT_MAX;
        
        for ($j = 0; $j < $numVertices; $j++) {
            if ($selected[$j] == false && $graph[$i][$j] < $minVal) {
                $minKey = $j;
                $minVal = $graph[$i][$j];
            }
        }

        $selected[$minKey] = true;
        $parent[$minKey] = $i;
        $minWeight += $minVal;
    }

    return $minWeight;
}

二、Kruskal演算法

Kruskal演算法是一種基於邊的貪心演算法，它首先將所有邊按權重從小到大排序，然後逐一加入生成樹中，如果加入的邊不形成環路，則加入最小生成樹的邊集合中。具體步驟如下：

1. 對所有邊按權重從小到大進行排序。
2. 從權重最小的邊開始，逐一加入生成樹的邊集合。
3. 如果加入的邊不形成環路，則將該邊加入最小生成樹。
4. 重複步驟2和3，直到生成樹的邊數等於頂點數減一。
5. 最終得到的邊集合就是最小生成樹。

以下是用PHP實作Kruskal演算法的程式碼範例：

function find($parent, $i) {
    if ($parent[$i] == -1) {
        return $i;
    }

    return find($parent, $parent[$i]);
}

function union($parent, $x, $y) {
    $xSet = find($parent, $x);
    $ySet = find($parent, $y);

    $parent[$xSet] = $ySet;
}

function kruskal($edges, $numVertices) {
    $parent = array_fill(0, $numVertices, -1);
    $minWeight = 0;

    usort($edges, function ($a, $b) {
        return $a['weight'] - $b['weight'];
    });

    $e = 0; // 记录生成树的边数
    $i = 0;

    while ($e < $numVertices - 1) {
        $nextEdge = $edges[$i++];

        $x = find($parent, $nextEdge['src']);
        $y = find($parent, $nextEdge['dest']);

        if ($x != $y) {
            $minWeight += $nextEdge['weight'];
            union($parent, $x, $y);
            $e++;
        }
    }

    return $minWeight;
}

#總結：

本文詳細介紹了PHP中兩種最小生成樹演算法的原理和實現代碼。 Prim演算法和Kruskal演算法分別採用不同的貪心策略，能夠有效率地求解連通圖的最小生成樹。希望本文對讀者理解最小生成樹演算法在PHP的應用有所幫助。

以上是PHP中的最小生成樹演算法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！