Извлечение деревьев/DAG из циклического графика

Question

Учитывая заданный циклический график, как мне получить различные DAG/деревья, которые являются репрезентативными для входного графика? По сути, я хотел бы извлечь различные деревья из данной схемы (направленный & циклический) график. Любая помощь будет принята с благодарностью.

Answer 1

Использовать Prim или Kruskal's algos.
См. Сводку: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Undirected/

Answer 2

Это зависит от ваших требований. Если вы хотите иметь только DAG с наибольшим весом, я думаю, вы можете попытаться отсортировать все ребра, а затем удалить края один за другим в этом порядке, если край разбивает цикл.