Penjelasan terperinci tentang algoritma pokok rentang minimum dalam PHP

Penjelasan terperinci tentang algoritma pokok rentang minimum dalam PHP

Pokok Rentang Minimum (pendek kata MST) ialah konsep penting dalam teori graf, digunakan untuk menyelesaikan masalah memilih tepi berat minimum graf yang disambungkan. Dalam bahasa PHP, kita boleh mencapai fungsi ini melalui beberapa algoritma pokok rentang minimum klasik. Artikel ini akan memperkenalkan secara terperinci dua algoritma pokok rentang minimum yang biasa digunakan: algoritma Prim dan algoritma Kruskal, dan memberikan contoh kod PHP yang sepadan.

1. Algoritma Prim

Algoritma prim ialah algoritma tamak yang bermula dari puncak dan secara beransur-ansur mengembang untuk menjana pokok rentang minimum. Proses khusus adalah seperti berikut:

1. Pilih titik permulaan dan tambahkannya pada set yang dipilih.
2. Pilih tepi dengan berat terkecil daripada bucu bersebelahan dengan set bucu yang dipilih dan tambahkannya pada set tepi yang dipilih.
3. Tambah bucu yang disambungkan oleh tepi ini pada set bucu yang dipilih.
4. Ulang langkah 2 dan 3 sehingga semua bucu ditambahkan pada set yang dipilih.
5. Set akhir tepi ialah pokok rentang minimum.

Berikut ialah contoh kod untuk melaksanakan algoritma Prim dalam 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. Algoritma Kruskal

Algoritma Kruskal ialah algoritma tamak berasaskan tepi Ia mula-mula menyusun semua tepi mengikut berat dari kecil kepada besar, dan kemudian menambah mereka satu demi satu Dalam pokok rentang, jika kelebihan yang ditambah tidak membentuk kitaran, ia ditambah kepada set tepi pokok rentang minimum. Langkah-langkah khusus adalah seperti berikut:

1. Isih semua tepi mengikut berat dari kecil ke besar.
2. Mulakan dari tepi dengan berat yang paling kecil dan tambahkan ke set tepi pokok rentang satu demi satu.
3. Jika kelebihan tambahan tidak membentuk kitaran, tambahkan tepi kepada pokok rentang minimum.
4. Ulang langkah 2 dan 3 sehingga bilangan tepi dalam pokok rentang adalah sama dengan bilangan bucu tolak satu.
5. Set akhir tepi ialah pokok rentang minimum.

Berikut ialah contoh kod untuk melaksanakan algoritma Kruskal dalam 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;
}

Ringkasan:

Artikel ini memperincikan prinsip dan kod pelaksanaan dua algoritma pepohon rentang minimum dalam PHP. Algoritma Prim dan algoritma Kruskal masing-masing menggunakan strategi tamak yang berbeza dan boleh menyelesaikan pepohon rentang minimum graf bersambung dengan cekap. Saya harap artikel ini akan membantu pembaca memahami aplikasi algoritma pokok rentang minimum dalam PHP.

Atas ialah kandungan terperinci Penjelasan terperinci tentang algoritma pokok rentang minimum dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!