有向グラフのノードを並べ替えて、(並べ替え順序に反して) 逆方向に流れる矢印の数が最小限になるようにする必要があります。
アルゴリズムは考えられますが (スワップがなくなるまでノードをスワップし続けるなど)、アルゴリズムの実行速度や最適なソリューションに到達するかどうかはわかりません。
この問題の名前と複雑さは何ですか?
2 に答える
2
ノードを深さ順に並べ替えるには、トポロジカル 並べ替えを使用します。 ただし、これはサイクルを含まないグラフでのみ機能します。あなたの問題は、グラフにサイクルがあるように聞こえます。1 つのオプションは、サイクルを見つけて (これを行う方法については、カメとウサギのアルゴリズムを参照してください)、サイクルを壊して、どこで壊したかを記録することです。次に、ノードをソートして再リンクします。
視覚化の目的でこれを行っている場合は、GraphVizと呼ばれるグラフ レンダリング ライブラリがあり、説明していることと非常によく似た処理を行い、ノードをレイアウトします。統合して使用するのは簡単で、画面やさまざまな出力形式にレンダリングできます。
于 2009-04-21T08:18:11.760 に答える