Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah pengisihan topologi?

Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah pengisihan topologi?

Isihan topologi ialah masalah klasik dalam teori graf Matlamat utamanya ialah untuk mengisih graf akiklik berarah (DAG) supaya semua bucu dalam graf memenuhi syarat bahawa darjah dalam adalah kurang daripada atau sama dengan darjah keluar. . Pengisihan topologi digunakan secara meluas dalam banyak senario, seperti penjadualan tugas, reka bentuk pengkompil, dsb.

Dalam artikel ini, kami akan memperkenalkan penyelesaian yang cekap untuk melaksanakan pengisihan topologi menggunakan bahasa PHP. Pertama, kita akan membincangkan prinsip asas algoritma pengisihan topologi, dan kemudian memberikan contoh kod khusus.

1. Prinsip algoritma pengisihan topologi

Algoritma pengisihan topologi terutamanya berdasarkan idea carian pertama mendalam (DFS) atau carian pertama keluasan (BFS). Khususnya, algoritma pengisihan topologi mengandungi langkah-langkah berikut:

a) Pertama, kita perlu membina perwakilan senarai bersebelahan bagi graf terarah, di mana setiap bucu berfungsi sebagai indeks tatasusunan, dan kemudian bucu yang ditunjuk oleh bucu berfungsi sebagai nilai tatasusunan.

b) Kemudian, kami memilih bucu dengan dalam darjah 0 daripada graf sebagai bucu permulaan dan menambahnya pada baris gilir.

c) Seterusnya, kami mengulangi atas bucu dalam baris gilir dan mengurangkan dalam darjah bucu bersebelahan dengan 1. Jika dalam darjah bucu bersebelahan ialah 0, tambahkannya pada baris gilir.

d) Ulang proses di atas sehingga barisan kosong. Akhir sekali, bucu dalam baris gilir yang diperoleh adalah hasil pengisihan topologi.

2. Pelaksanaan kod algoritma pengisihan topologi

Berikut ialah contoh kod menggunakan bahasa PHP untuk melaksanakan algoritma pengisihan topologi:

class Graph {
    private $adjList;

    public function __construct() {
        $this->adjList = [];
    }

    public function addEdge($src, $dest) {
        if (!isset($this->adjList[$src])) {
            $this->adjList[$src] = [];
        }
        $this->adjList[$src][] = $dest;
    }

    public function topologicalSort() {
        $inDegree = [];
        foreach ($this->adjList as $src => $destList) {
            $inDegree[$src] = 0;
        }

        foreach ($this->adjList as $src => $destList) {
            foreach ($destList as $dest) {
                $inDegree[$dest]++;
            }
        }

        $queue = new SplQueue();
        foreach ($inDegree as $src => $in) {
            if ($in == 0) {
                $queue->enqueue($src);
            }
        }

        $result = [];

        while (!$queue->isEmpty()) {
            $src = $queue->dequeue();
            $result[] = $src;

            if (isset($this->adjList[$src])) {
                foreach ($this->adjList[$src] as $dest) {
                    $inDegree[$dest]--;
                    if ($inDegree[$dest] == 0) {
                        $queue->enqueue($dest);
                    }
                }
            }
        }

        return $result;
    }
}

$g = new Graph();
$g->addEdge(1, 3);
$g->addEdge(1, 4);
$g->addEdge(2, 4);
$g->addEdge(3, 5);
$g->addEdge(4, 5);

$result = $g->topologicalSort();

foreach ($result as $vertex) {
    echo $vertex . ' ';
}

Dalam kod di atas, kelas Graf pertama kali ditakrifkan, yang mengandungi pembina dan kaedah addEdge untuk menambah tepi dan kaedah pengisihan topologi. Dalam fungsi utama, kami mencipta graf terarah dan melakukan pengisihan topologi, dan akhirnya mengeluarkan hasil mengikut pengisihan topologi.

Ringkasan:

Dengan menerangkan prinsip dan pelaksanaan khusus algoritma pengisihan topologi, dan menggabungkannya dengan contoh kod, penyelesaian yang cekap dilaksanakan dalam bahasa PHP. Pengisihan topologi boleh memainkan peranan penting dalam banyak aplikasi praktikal dan membantu kami menyelesaikan pelbagai masalah penjadualan tugas dan pergantungan.

Atas ialah kandungan terperinci Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah pengisihan topologi?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!