Bagaimana untuk menulis algoritma pengisihan topologi menggunakan PHP

Cara menulis algoritma pengisihan topologi menggunakan PHP

Isihan topologi ialah algoritma untuk menyusun graf akiklik terarah (DAG). Prinsipnya adalah untuk mengisih nod dalam graf mengikut kebergantungan untuk memastikan bahawa arah semua tepi dalam hasil pengisihan adalah konsisten. Dalam pembangunan sebenar, pengisihan topologi sering digunakan untuk menyelesaikan masalah seperti penjadualan tugas dan analisis kebergantungan. Artikel ini akan memperkenalkan cara menulis algoritma pengisihan topologi menggunakan PHP, dengan contoh kod.

Idea algoritma:

1. Buat tatasusunan dalam darjah untuk menyimpan dalam darjah setiap nod (iaitu, berapa banyak nod menunjuk ke nod ini
2. Buat tatasusunan hasil untuk menyimpan hasil pengisihan
3. ; Traverse Untuk nod dalam graf, kira dalam darjah setiap nod dan simpannya dalam tatasusunan dalam darjah
4. Mulakan baris gilir dan tambah semua nod dengan darjah 0 pada baris gilir; baris gilir tidak kosong, secara berurutan Nyah gilir nod daripada baris gilir dan tambahkannya pada tatasusunan hasil
5. Traverse nod jiran nod dan kurangkan dalam darjah setiap nod jiran sebanyak
6. Jika dalam darjah nod jiran dikurangkan kepada 0, kemudian Enqueue ia; berjaya; jika tidak, terdapat kitaran dalam graf dan pengisihan topologi tidak dapat dilakukan.
7. Berikut ialah contoh kod algoritma pengisihan topologi PHP yang ditulis berdasarkan idea di atas:

8. <?php
   
   function topologicalSort($graph) {
       $inDegree = []; // 入度数组
       $result = []; // 排序结果
       $queue = new SplQueue(); // 队列
   
       // 初始化入度数组
       foreach ($graph as $node => $neighbors) {
           $inDegree[$node] = 0;
       }
   
       // 计算入度数组
       foreach ($graph as $node => $neighbors) {
           foreach ($neighbors as $neighbor) {
               $inDegree[$neighbor]++;
           }
       }
   
       // 将入度为0的节点入队
       foreach ($inDegree as $node => $degree) {
           if ($degree == 0) {
               $queue->enqueue($node);
           }
       }
   
       // 队列不为空时
       while (!$queue->isEmpty()) {
           $node = $queue->dequeue();
           $result[] = $node;
   
           // 遍历邻居节点
           foreach ($graph[$node] as $neighbor) {
               $inDegree[$neighbor]--;
               if ($inDegree[$neighbor] == 0) {
                   $queue->enqueue($neighbor);
               }
           }
       }
   
       // 判断是否成功排序
       if (count($result) == count($graph)) {
           return $result;
       } else {
           return false;
       }
   }
   
   // 测试用例
   $graph = [
       'A' => ['B', 'C'],
       'B' => ['C', 'D'],
       'C' => ['E'],
       'D' => ['F'],
       'E' => [],
       'F' => ['G'],
       'G' => []
   ];
   
   $result = topologicalSort($graph);
   if ($result) {
       echo "拓扑排序结果: " . implode(' -> ', $result) . "
   ";
   } else {
       echo "图中存在环，无法进行拓扑排序。
   ";
   }
   
   ?>

Dalam kod di atas,
9. dalam tatasusunan. Selepas menjalankan kod, hasil pengisihan topologi akan dikeluarkan.

Ringkasan:

Artikel ini memperkenalkan cara menggunakan PHP untuk menulis algoritma pengisihan topologi dan memberikan contoh kod yang sepadan. Pengisihan topologi ialah algoritma praktikal yang sering digunakan untuk menyelesaikan masalah seperti penjadualan tugas. Menguasai algoritma pengisihan topologi akan membantu meningkatkan keupayaan pemprosesan graf akiklik terarah dan memberikan sokongan untuk pelbagai analisis kebergantungan semasa pembangunan. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma pengisihan topologi menggunakan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!