я есть два взвешенных DAG (направленных ациклических графа), и мне нужно объединить их в один, чтобы я мог получить топологический порядок (в некоторых случаях это может быть больше двух). Проблема в том, что каждый график ацикличен, но может образовывать цикл вместе. Кроме того, графики большие (100 тыс. + Узлов, 500 тыс. + Ребер). Есть ли умный способ объединить графики? Не менее хорошим будет алгоритм для прохождения всех графиков «сразу».

Редактировать:

Под «слиянием» я подразумеваю объединение всех ребер и вершин обоих графов вместе (конечно, с сохранением весов), если они не создают циклы. Если ребро уже существует, я хочу использовать для него больший вес.

Идея состоит в том, что начинание с двух ациклических графов должно дать преимущество перед простым «исправлением» результата впоследствии (это будет означать, что нужно найти набор дуг обратной связи, который является NP трудным, поэтому я хотел избежать этого).

Спасибо вам за ваши предложения.