algorithm - 以前のことを知っているアイテムの並べ替え

Question

私はアイテムのセットを持っています。各アイテムには、IDとPREVIOUS_IDフィールドがあります。それらを効率的にソートし、サイクル（エラー状態）を検出するにはどうすればよいですか？

複雑にするために、それらを単一のシーケンスでソートする必要がありますが、複数のアイテムが同じPREVIOUS_IDを持っている可能性があります。

Answer 1

ランダムに1つを選択し、前のアイテムがなくなるまで前のIDパスをたどります。その時点で、アイテムが残っていない場合は、最初に選択していないアイテムを選択して、最初からやり直します。

サイクルを検出できるように、常に訪問済みアイテムのセットを維持してください。