G=(V,E)DAGにしましょう。Vはグラフ内の頂点のセットで、 はE頂点を接続するエッジのセットですV。
グラフにノイズが導入されたと仮定します。つまり、いくつかの存在しないエッジが に挿入されEます。この上：
- ルートはグラフ内で「隠され」、内部ノードになる場合があります
- 葉も内部ノードになる可能性があります
- サイクルがグラフに挿入されます
最初の DAG のトポロジを維持しながらサイクルを削除するアルゴリズムを探しています。今のところ DFS を使用しています。ループに遭遇すると、ループを構成するエッジの 1 つが削除されます。ただし、根や葉の回復を保証するものではありません。最先端の有用なものを見つけることができますか?
前もって感謝します。