次の基準に従ってサンプル ノードを効率的に描画したい、大きな有向非環状グラフ (DAG) があります。
ノードは、それらが参照する他のノードへのポインターを持つオブジェクトとして格納されます。グラフ全体は、他のすべてを直接的または間接的に参照する単一のルート ノードから到達できます。
これを行うための適切なアルゴリズムはありますか? DAG は大きいため、大量の追加メモリを必要としないのが理想的です。
私が思いつくことができる唯一の解決策は、
ノードをハッシュセットに入れます
（たとえば、幅優先トラバーサルを使用してルートからそれらをトラバースします）、O（| E | + | V |）
ノード A から開始し、エッジを後方にトラバースしてすべての先行ノードを削除します
(再び O(|E|+|V|))
残りのノードからランダムなノードを選択します。
これにより、O(|V|) メモリ要件を持つ O(|E|+|V|) アルゴリズムが発生します。
手順 1 でノードをコピーする必要はなく、ノードへの参照を保存するだけであることに注意してください。
私は決してこの分野の専門家ではありませんが、 Metropolis-HastingsやGibbs サンプリングアルゴリズムなどのモンテカルロ マルコフ連鎖サンプリング法が必要になると思います。
いくつかのコード サンプルをオンラインで見つけることができます。コードを変更して、目的の処理を正確に実行する必要がある場合があります。このトピックに関するいくつかの優れたプレゼンテーションがあります。
あなたを助けるかもしれないいくつかのソフトウェアは次のとおりです。
あなたがグラフ理論に精通しているかどうかはわかりませんので、これを実装するのがどれほど難しいかわかりません。
これがお役に立てば幸いです...