PHPの最小スパニングツリーアルゴリズムの詳細な説明

PHP の最小スパニング ツリー アルゴリズムの詳細な説明

最小スパニング ツリー (最小スパニング ツリー、MST と呼ばれる) は、グラフ理論の重要な概念であり、最小値の選択の問題を解決するために使用されます。接続されたグラフの重みエッジ。 PHP 言語では、いくつかの古典的な最小スパニング ツリー アルゴリズムを通じてこの関数を実装できます。この記事では、一般的に使用される 2 つの最小スパニング ツリー アルゴリズム、Prim のアルゴリズムと Kruskal のアルゴリズムを詳しく紹介し、対応する PHP コード例を示します。

1. 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;
}

2. Kruskal アルゴリズム

Kruskal アルゴリズムは、エッジベースの貪欲アルゴリズムです。最初にすべてのエッジを重みの小さいものから大きいものにソートし、1 つずつスパニング ツリーに追加します。追加されたエッジが循環を形成しない場合は、最小スパニング ツリーのエッジ セットに追加されます。具体的な手順は次のとおりです。

1. すべてのエッジを重みで小さいものから大きいものまで並べ替えます。
2. 重みが最も小さいエッジから開始して、スパニング ツリーのエッジ セットに 1 つずつ追加します。
3. 追加したエッジが循環を形成しない場合は、最小全域木にエッジを追加します。
4. スパニング ツリー内のエッジの数が頂点の数から 1 を引いた数に等しくなるまで、手順 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;
}

概要:

この記事では、2 つの最小スパンの原理と原則について詳しく紹介します。 PHP のツリー アルゴリズム コードを実装します。 Prim のアルゴリズムと Kruskal のアルゴリズムは、それぞれ異なる貪欲戦略を採用しており、接続されたグラフの最小スパニング ツリーを効率的に解くことができます。この記事が、読者が PHP における最小スパニング ツリー アルゴリズムのアプリケーションを理解するのに役立つことを願っています。

以上がPHPの最小スパニングツリーアルゴリズムの詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。