有向グラフに1つのトポロジカルソートが1つしかないかどうかチェック

Question

有向グラフに1つのトポロジカルな順序が1つしかないかどうかをチェックするアルゴリズムの疑似コードを作成しようとしています。私はすでにトポロジカルソート（DFSを使用）の擬似コードを考え出していますが、それは私にはあまり役立たないようです。そのグラフにシンクがないのだろうか？トポロジカルな順序は1つではありません（それは役に立ちますか？）。

Answer 1

これは、エッジが出ない頂点で開始すると、可能な限り最良の実行時間が改善されるため、this answerの改善です。トポロジカルソートLを取得する

あなたの有向グラフがN頂点を持っており、あなたは入次数0と正確に一つの開始頂点を持っている場合は、

• ドゥDFS（だけ開始頂点上）。
• Lに頂点がない場合は、頂点に到達できない（サイクルの一部）か、別の開始頂点が必要です（複数のtoposortsがあるため）。 [0,N-2]でiについては
、
• L[i]からL[i+1]へのエッジが存在しない場合、
  • 戻り偽。
• trueを返します。

---

あるいは、カーンのアルゴリズムを変更しますアルゴリズムの実行中に複数の頂点が（入次数0の頂点の）セット内にある場合、falseを返します。それ以外の場合はtrueを返します。