有向巡回グラフが与えられた場合、入力グラフを表すさまざまな DAG/ツリーを取得するにはどうすればよいですか? 実際には、指定された回路 (有向および巡回) グラフからさまざまなツリーを抽出したいと考えています。
1283 次
2 に答える
0
Prim または Kruskal のアルゴリズムを使用します。
要約を参照してください: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Undirected/
于 2012-01-05T18:29:39.447 に答える
0
それはあなたの要件に依存します。最高の重みの DAG のみが必要な場合は、すべてのエッジを並べ替えてから、エッジがサイクルを破る場合は、その順序でエッジを 1 つずつ削除できると思います。
于 2013-07-23T17:13:05.327 に答える