在C＃中，如何找到循环依赖链？
当一个部署项目包含第二个部署项目的项目输出，而第二个项目包含第一个项目的输出时，通常会发生此错误。
我有一个检查循环依赖的方法。 在输入中，我们有一个字典，其中包含例如<"A", >和<"B", > ，这意味着A取决于在B和C ，我们与A->B有循环依赖关系。
但通常我们会有一个更复杂的情况，有一连串的依赖。 如何修改此方法以查找依赖链？ 例如，我想要一个包含链A->B->A的变量，而不是A类与B类冲突。
private void FindDependency(IDictionary<string, IEnumerable> serviceDependence)
在图中查找循环的简单方法是使用递归深度优先图着色算法，其中节点被标记为“访问”或“访问”。 如果在访问节点时发现它已处于“访问”状态，则表示您有一个循环。 标记为“已访问”的节点可以被跳过。 例如：
public class DependencyExtensions { enum VisitState { NotVisited, Visiting, Visited }; public static TValue ValueOrDefault(this IDictionary dictionary, TKey key, TValue defaultValue) { TValue value; if (dictionary.TryGetValue(key, out value)) return value; return defaultValue; } static void DepthFirstSearch(T node, Func> lookup, List parents, Dictionary visited, List> cycles) { var state = visited.ValueOrDefault(node, VisitState.NotVisited); if (state == VisitState.Visited) return; else if (state == VisitState.Visiting) { // Do not report nodes not included in the cycle. cycles.Add(parents.Concat(new[] { node }).SkipWhile(parent => !EqualityComparer .Default.Equals(parent, node)).ToList()); } else { visited[node] = VisitState.Visiting; parents.Add(node); foreach (var child in lookup(node)) DepthFirstSearch(child, lookup, parents, visited, cycles); parents.RemoveAt(parents.Count - 1); visited[node] = VisitState.Visited; } } public static List> FindCycles (this IEnumerable nodes, Func> edges) { var cycles = new List>(); var visited = new Dictionary(); foreach (var node in nodes) DepthFirstSearch(node, edges, new List (), visited, cycles); return cycles; } public static List> FindCycles(this IDictionary listDictionary) where TValueList : class, IEnumerable { return listDictionary.Keys.FindCycles(key => listDictionary.ValueOrDefault(key, null) ?? Enumerable.Empty ()); } }
然后，您可以使用它：
var serviceDependence = new Dictionary> { { "A", new List { "A" }}, { "B", new List { "C", "D" }}, { "D", new List { "E" }}, { "E", new List { "F", "Q" }}, { "F", new List { "D" }}, }; var cycles = serviceDependence.FindCycles(); Debug.WriteLine(JsonConvert.SerializeObject(cycles, Formatting.Indented)); foreach (var cycle in cycles) { serviceDependence[cycle[cycle.Count - 2]].Remove(cycle[cycle.Count - 1]); } Debug.Assert(serviceDependence.FindCycles().Count == 0);
更新
您的问题已更新，以请求“最有效的算法”来查找循环依赖项。 原始答案中的代码是递归的，因此可能会有数千个级别的依赖链StackOverflowException 。 这是一个带有显式堆栈变量的非递归版本：
public static class DependencyExtensions { enum VisitState { NotVisited, Visiting, Visited }; public static TValue ValueOrDefault(this IDictionary dictionary, TKey key, TValue defaultValue) { TValue value; if (dictionary.TryGetValue(key, out value)) return value; return defaultValue; } private static void TryPush(T node, Func> lookup, Stack>> stack, Dictionary visited, List> cycles) { var state = visited.ValueOrDefault(node, VisitState.NotVisited); if (state == VisitState.Visited) return; else if (state == VisitState.Visiting) { Debug.Assert(stack.Count > 0); var list = stack.Select(pair => pair.Key).TakeWhile(parent => !EqualityComparer .Default.Equals(parent, node)).ToList(); list.Add(node); list.Reverse(); list.Add(node); cycles.Add(list); } else { visited[node] = VisitState.Visiting; stack.Push(new KeyValuePair>(node, lookup(node).GetEnumerator())); } } static List> FindCycles (T root, Func> lookup, Dictionary visited) { var stack = new Stack>>(); var cycles = new List>(); TryPush(root, lookup, stack, visited, cycles); while (stack.Count > 0) { var pair = stack.Peek(); if (!pair.Value.MoveNext()) { stack.Pop(); visited[pair.Key] = VisitState.Visited; pair.Value.Dispose(); } else { TryPush(pair.Value.Current, lookup, stack, visited, cycles); } } return cycles; } public static List> FindCycles (this IEnumerable nodes, Func> edges) { var cycles = new List>(); var visited = new Dictionary(); foreach (var node in nodes) cycles.AddRange(FindCycles(node, edges, visited)); return cycles; } public static List> FindCycles(this IDictionary listDictionary) where TValueList : class, IEnumerable { return listDictionary.Keys.FindCycles(key => listDictionary.ValueOrDefault(key, null) ?? Enumerable.Empty ()); } }
这在N*log(N) + E处应该是合理有效的，其中N是节点数， E是边数。 Log(N)来自构建visited哈希表，可以通过使每个节点记住其VisitState来消除。 这看起来相当合理; 在以下测试工具中，在10000个节点中找到17897个平均长度为4393的周期，总共125603个依赖关系的时间大约为10.2秒：
public class TestClass { public static void TestBig() { var elapsed = TestBig(10000); Debug.WriteLine(elapsed.ToString()); } static string GetName(int i) { return "ServiceDependence" + i.ToString(); } public static TimeSpan TestBig(int count) { var serviceDependence = new Dictionary>(); for (int iItem = 0; iItem < count; iItem++) { var name = GetName(iItem); // Add several forward references. for (int iRef = iItem - 1; iRef > 0; iRef = iRef / 2) serviceDependence.Add(name, GetName(iRef)); // Add some backwards references. if (iItem > 0 && (iItem % 5 == 0)) serviceDependence.Add(name, GetName(iItem + 5)); } // Add one backwards reference that will create some extremely long cycles. serviceDependence.Add(GetName(1), GetName(count - 1)); List> cycles; var stopwatch = new Stopwatch(); stopwatch.Start(); try { cycles = serviceDependence.FindCycles(); } finally { stopwatch.Stop(); } var elapsed = stopwatch.Elapsed; var averageLength = cycles.Average(l => (double)l.Count); var total = serviceDependence.Values.Sum(l => l.Count); foreach (var cycle in cycles) { serviceDependence[cycle[cycle.Count - 2]].Remove(cycle[cycle.Count - 1]); } Debug.Assert(serviceDependence.FindCycles().Count == 0); Console.WriteLine(string.Format("Time to find {0} cycles of average length {1} in {2} nodes with {3} total dependencies: {4}", cycles.Count, averageLength, count, total, elapsed)); Console.ReadLine(); System.Environment.Exit(0); return elapsed; } }
构建一个包含每个输入的所有直接依赖关系的字典。 对于其中的每一个，添加所有唯一的间接依赖项（例如，遍历给定项的每个依赖项，如果父项不存在，则添加它）。 只要您对字典进行至少一次更改，就重复此操作。 如果有一个项目本身就有它的依赖项，那就是一个周期性的依赖:)
当然，这是相对低效的，但它非常简单易懂。 如果您正在创建编译器，您可能只需构建所有依赖项的有向图，并搜索其中的路径 – 您可以找到许多用于在有向图中查找路径的现成算法。
拓扑排序是这样做的方法。 我在Vb.net中有一个实现