У меня есть набор данных, для которых мне нужно выполнить топологическую сортировку, с несколькими предположениями и ограничениями, и мне было интересно, знает ли кто-нибудь существующий эффективный алгоритм, который подойдет для этого.
- Известно, что отношения данных образуют группу обеспечения доступности баз данных (поэтому не нужно беспокоиться о циклах).
- Край от A до B указывает, что A зависит от B, поэтому B должен отображаться перед A в топологической структуре.упорядоченность.
- График не обязательно связан;то есть для любых двух узлов N и M не может быть способа добраться от N до M по следующим ребрам (даже если вы игнорируете направление ребра).
- Связи данных однозначно связаны.Это означает, что когда существует ребро, направленное из А в В, только узел А содержит информацию о существовании ребра.
Проблема может быть сформулирована следующим образом:
Учитывая набор узлов S в графе G, которые могут иметь или не иметь входящие ребра , найти топологическое упорядочение подграфа G', состоящего из всех узлов в G которые достижимы из любого узла в наборе S (подчиняются направлению ребра).
Это мешает обычным подходам к топологической сортировке, поскольку они требуют, чтобы узлы в наборе S не имели каких-либовходящие ребра, что не так в моем случае.Патологический случай:
A --> B --> D
| ^ ^
| | |
\---> C ----/
, где S = {B, C}.Подходящим порядком будет D, B, C, но если обычный алгоритм топологической сортировки учитывает B до C, он в итоге получит C, D, B, что совершенно неверно.(Обратите внимание, что A не появляется в результирующем порядке, поскольку он недоступен с S; здесь приведен пример, где все узлы в S могут иметь входящие ребра)
ТеперьЯ должен представить, что это давно решенная проблема, так как это, по сути, то, что программы, такие как apt и yum, должны делать, когда вы указываете несколько пакетов в одной команде установки.Однако, когда я ищу ключевые фразы, такие как «алгоритм разрешения зависимостей», я получаю результаты, описывающие нормальную топологическую сортировку, которая не обрабатывает этот конкретный случай.
Я могу придумать пару способов сделать это, но ни один из них не выглядит особенно элегантным.Мне было интересно, есть ли у кого-нибудь указатели на соответствующий алгоритм, предпочтительно такой, который может работать за один проход данных.