PHP アルゴリズム設計のアイデア: トポロジカルソート問題に対する効率的な解決策を達成するには?

PHP アルゴリズム設計のアイデア: トポロジカル ソート問題に対する効率的な解決策を実現するにはどうすればよいでしょうか?

トポロジカル ソートは、グラフ理論における古典的な問題です。その主な目的は、グラフ内のすべての頂点が次数以下であるという条件を満たすように、有向非巡回グラフ (DAG) をソートすることです。出次数。トポロジカル ソートは、タスク スケジューリング、コンパイラ設計など、多くのシナリオで広く使用されています。

この記事では、PHP 言語を使用してトポロジカル ソートを実装するための効率的なソリューションを紹介します。まず、トポロジカルソートアルゴリズムの基本原理について説明し、次に具体的なコード例を示します。

1. トポロジカル ソート アルゴリズムの原理

トポロジカル ソート アルゴリズムは、主に深さ優先検索 (DFS) または幅優先検索 (BFS) の考えに基づいています。具体的には、トポロジカル ソート アルゴリズムには次のステップが含まれます。

a) まず、有向グラフの隣接リスト表現を構築する必要があります。ここで、各頂点は配列のインデックスとして機能し、次に頂点が指すものとなります。頂点を配列値として指定します。

b) 次に、グラフから次数 0 の頂点を開始頂点として選択し、それをキューに追加します。

c) 次に、キュー内の頂点をトラバースし、隣接する頂点の入次数を 1 減らします。隣接する頂点の入次数が 0 の場合、それをキューに追加します。

d) キューが空になるまで上記のプロセスを繰り返します。最後に、取得されたキュー内の頂点は、トポロジカル ソートの結果です。

2. トポロジカル ソート アルゴリズム コードの実装

以下は、PHP 言語を使用してトポロジカル ソート アルゴリズムを実装するコード例です:

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

上記のコードでは、Graph クラス最初に定義されます。これには、コンストラクター、エッジを追加するためのメソッド addEdge、およびトポロジカルな並べ替えのためのメソッド topologicalSort が含まれています。 main 関数では、有向グラフを作成してトポロジカル ソートを実行し、最後にトポロジカル ソートに従って結果を出力します。

概要:

トポロジカル ソート アルゴリズムの原理と具体的な実装を説明し、コード例と組み合わせることで、効率的なソリューションが PHP 言語で実装されます。トポロジカルソートは多くの実際のアプリケーションで重要な役割を果たし、さまざまなタスクのスケジューリングや依存関係の問題の解決に役立ちます。

以上がPHP アルゴリズム設計のアイデア: トポロジカルソート問題に対する効率的な解決策を達成するには?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。