graph-algorithm - 有向グラフが一意の位相順序を持っているかどうかを判断するアルゴリズムを設計する

Question

有向グラフに一意のトポロジー順序があるかどうかを判断するアルゴリズムを設計します...トポロジー順序の連続する頂点の各ペア間に有向エッジがある場合にのみ、有向グラフに一意のトポロジー順序があることがわかっているため..しかし、どうすればできますかそれを決定するアルゴリズムを設計しますか？

Answer 1

一意のトポロジカル順序は、完全なタスクを実行できるサブタスクのシーケンスが1つしかないことを意味します。これは、選択の余地がないことを意味します。したがって、グラフはリストである必要があります。つまり、一方のタスクが他方に依存し、他方に依存するというようになります。