循環グラフから木/ DAGを抽出する

Question

有向循環グラフを考えると、入力グラフを表すさまざまなDAG /ツリーをどのように取得できますか？実際には、与えられた回路（指示された&周期）グラフからさまざまな木を抽出したいと思います。どんな助けでも大歓迎です。

Answer 1

プリムまたはクルスカルの藻類を使用してください。
要約を表示：http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Undirected/

Answer 2

これは要件によって異なります。 DAGが最も重視されたいのであれば、すべてのエッジを並べ替えることができます。そして、エッジが1つのサイクルを壊した場合、その順番でエッジを1つずつ削除してください。