Поиск всех топологических порядков

Question

Мне нужно создать алгоритм, который находит все топологические порядки (с использованием подсчета предшественников) и пути с самой высокой стоимостью и их стоимость между 2 парами вершин. Мой алгоритм на данный момент выглядит так:

 def topologicalSort(self):
        sorted = []
        count = {}
        q = deque()
        for x in self.parseX():
            count[x] = self.innerDegree(x)
            if count[x] == 0:
                q.append(x)
        while len(q) > 0:
            x = q.popleft()
            sorted.append(x)
            for y in self.parseNout(x):
                count[y] -= 1
                if count[y] == 0:
                    q.append(y)
        return sorted

Он работает нормально, но проблема в том, что он найдет только один топологический порядок. И мой вопрос: как я могу найти все топологические порядки?

Answer 1

Ваши петли в фиксированном порядке. Различные топологические виды достигаются путем их перебора в разном порядке. Итак, вам нужен другой уровень рекурсии, пытаясь топологически сортировать каждый из них, который будет опробован первым. языков):

• https://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/
• https://www.techiedelight.com/find-all-possible-topological-orderings-of-dag/