トポロジカルソートのDAGを生成するためのランダムアルゴリズムを知っている人はいますか。アルゴリズムを呼び出すたびに、有効なトポロジカルソートのDAGがすべて生成される確率がゼロではありません。
アルゴリズムが有効なトポロジカルソートを排除しないことが重要です。これは、十分な反復が与えられると、特定のDAGのすべてのトポロジカルソートを明らかに検出できる必要がある、より大きなアルゴリズムの一部であるためです。
そのようなアルゴリズムが開発されたかどうか誰かが知っていますか？
（あるいは、特定のDAGのすべてのトポロジーの種類を生成することが保証されている合理的に効率的なアルゴリズムを誰かが知っている場合、私はおそらくそれを微調整して必要なものを取得できます。）
考えられるすべてのトポロジーの種類をカバーしていると言うことの意味を考えると役立ちます。トポロジカルソート中に、有効な候補のサブセットから処理する候補を選択するポイントがあります。各候補は有効な選択肢です。TSを実装する方法に応じて、それぞれが候補（発信エッジのセット）であるエッジのセット、または開始点（シンク/ソースのセット）として選択するノード、またはランダムに選択された開始ノード。
必要なのは、選択プロセスで、候補の特定のサブセットに対して圧倒的なバイアスがない分布が生成されるようにすることです。
選択プロセスにバイアスをかけて、無限に実行することなく、より均一な分布を実現できます。たとえば、セットの各候補に重みを割り当てることができます。候補が選択されるたびに、その候補の重みを「X」だけ減らし、他の候補の重みを「X /（k-1）」だけ増やします。ここで、kは候補セットのセットのサイズです。 。これにより、選択されなかった候補が次の反復で選択される可能性が高くなり、より均一な分布への収束が速くなります。