私が理解していることから、強く接続されたコンポーネントに対して既製の効率的なブラックボックスメソッドがある場合、トポロジカルソートを行う1つの方法は次のとおりです。
(仮定 - 自己ループなし)
- 強連結成分を実行する
- サイズ > 1 のコンポーネントが 1 つ以上ある場合、このグラフにはサイクルがあります。
- それ以外の場合 (グラフには 1 つのサイズのコンポーネントしかありません)、これは DAG です。おめでとうございます!
- それが DAG 実行のトポロジカル ソートである場合は、それができないと文句を言います。
効率に関係なく、上記はトポロジカルソートを行う「技術的に正しい」方法ですか?
物事を正しく理解していることを確認したいだけです。