мне нужно найти циклическую зависимость между классами, и я сразу же помнить две вещи из «Алгоритмы и структуры данных» курса:Каков алгоритм поиска круговой зависимости в проекте?
1) Нахождение Петлю в односвязный список (Флойда Cycle-Finding алгоритма)
2) поиск в глубину
Итак, у меня есть метод, который проверить циклическую зависимость
private void FindDependency(IDictionary<string, IEnumerable<string>> serviceDependence)
В вход, у нас есть словарь, который содержит, например, <"A", < "B", "C" >>
и <"B", < "A", "D" >>
, это означает, что класс A
зависит от класса B
и C
. На выходе мы имеем круговую зависимость между A->B
(в более сложной ситуации это будет цепочка зависимости).
Какие алгоритмы следует использовать и почему?
Создание dfs-дерева вашего графика зависимостей и поиск задних кромок будут работать нормально. – sashas
это дубликат http://stackoverflow.com/questions/29703972/in-c-how-to-find-chain-of-circular-dependency –
, если вы не хотите только проверять эти циклы, но также выполняют топологическую сортировку: они обычно находят циклы в любом случае (за сбой) – Carsten