Учитывая направленный циклический граф, как я могу получить различные DAG / деревья, которые представляют входной граф? По сути, я хотел бы извлечь различные деревья из данного контура (направленного и циклического) графа. Любая помощь будет принята с благодарностью.
Это зависит от ваших требований.Если вы хотите иметь DAG с наибольшим весом, я думаю, вы можете попытаться отсортировать все ребра, а затем удалить ребра по одному в этом порядке, если ребро нарушает цикл.
Используйте Prim или Kruskal's algos. См. Резюме: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Graph/Undirected/