Explication détaillée de l'algorithme d'arbre couvrant minimum en PHP

Explication détaillée de l'algorithme du Spanning Tree minimum en PHP

Le Minimum Spanning Tree (MST en abrégé) est un concept important dans la théorie des graphes, utilisé pour résoudre le problème de la sélection du bord de poids minimum d'un graphe connecté. Dans le langage PHP, nous pouvons implémenter cette fonction via certains algorithmes classiques de spanning tree minimum. Cet article présentera en détail deux algorithmes d'arbre couvrant minimum couramment utilisés : l'algorithme de Prim et l'algorithme de Kruskal, et donnera des exemples de code PHP correspondants.

1. Algorithme Prim

L'algorithme Prim est un algorithme glouton qui part d'un sommet et se développe progressivement pour générer un arbre couvrant minimum. Le processus spécifique est le suivant :

1. Sélectionnez un sommet de départ et ajoutez-le à l'ensemble sélectionné.
2. Sélectionnez l'arête avec le plus petit poids parmi les sommets adjacents à l'ensemble de sommets actuellement sélectionné et ajoutez-la à l'ensemble d'arêtes sélectionné.
3. Ajoutez les sommets connectés par cette arête à l'ensemble de sommets sélectionné.
4. Répétez les étapes 2 et 3 jusqu'à ce que tous les sommets soient ajoutés à l'ensemble sélectionné.
5. L'ensemble final d'arêtes est l'arbre couvrant minimum.

Ce qui suit est un exemple de code pour implémenter l'algorithme de Prim en PHP :

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. Algorithme de Kruskal

L'algorithme de Kruskal est un algorithme glouton basé sur les bords. Il trie d'abord tous les bords par poids, du plus petit au plus grand, puis les ajoute. les un par un. Dans un arbre couvrant, si l'arête ajoutée ne forme pas un cycle, elle est ajoutée à l'ensemble d'arêtes de l'arbre couvrant minimum. Les étapes spécifiques sont les suivantes :

1. Triez tous les bords par poids du petit au grand.
2. Commencez par le bord avec le plus petit poids et ajoutez-le un par un à l'ensemble des bords de l'arbre couvrant.
3. Si le bord ajouté ne forme pas un cycle, ajoutez le bord à l'arbre couvrant minimum.
4. Répétez les étapes 2 et 3 jusqu'à ce que le nombre d'arêtes dans l'arbre couvrant soit égal au nombre de sommets moins un.
5. L'ensemble final d'arêtes est l'arbre couvrant minimum.

Ce qui suit est un exemple de code pour implémenter l'algorithme de Kruskal en PHP :

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

Résumé :

Cet article détaille les principes et les codes d'implémentation de deux algorithmes d'arbre couvrant minimum en PHP. L'algorithme de Prim et l'algorithme de Kruskal adoptent respectivement des stratégies gloutonnes différentes et peuvent résoudre efficacement l'arbre couvrant minimum de graphes connectés. J'espère que cet article aidera les lecteurs à comprendre l'application de l'algorithme d'arbre couvrant minimum en PHP.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!