给定一个有向循环图，我如何获得代表输入图的各种 DAG/树？实际上，我想从给定的电路（有向和循环）图中提取各种树。
问问题
1283 次
2 回答
0
使用 Prim 或 Kruskal 的算法。
见摘要：http ://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Undirected/
于 2012-01-05T18:29:39.447 回答
0
这取决于您的要求。如果您只想拥有最高权重的DAG，我认为您可以尝试对所有边缘进行排序，然后如果边缘打破循环，则按该顺序一个接一个地删除边缘。
于 2013-07-23T17:13:05.327 回答