Учитывая направленный граф зависимостей, я хочу пройти этот граф с уровня корневого узла по уровню (сначала на ширину), однако, принимая узлы на каждом уровне в определенном порядке. В моем случае порядок узлов на каждом уровне должен быть отсортирован после глубины, прежде всего, для самых глубоких узлов.
Простой пример:
A -> B
B -> C
A -> C
Начиная с узла A, я хочу, чтобы travseral дал мне приказ A, B, C (а не A, C, B, потому что B имеет C под ним). Нет циклов.
Любые намеки высоко ценится. Я новичок в превосходной библиотеке JGraphT, поэтому, возможно, упустил из виду какое-то простое решение.
Один из способов решения этой проблемы:
- Найти все пути от root (A)
- Сортировка путей по длине (сначала самое высокое)
- Для каждого пути пройдитесь по узлам и поместите узел в нужное место в списке.
- Правильное место определяется линейным поиском списка в первой позиции, где новый узел не найден в списке
Но, возможно, уже есть какой-то встроенный алгоритм, поэтому яне нужно кодировать выше? : -)