QuickGraph – 是否有算法用于查找一组顶点的所有父项（直到根顶点）

在QuickGraph中 – 是否有算法用于查找一组顶点的所有父项（直到根顶点）。 换句话说，所有顶点都位于它们下面（在去往叶节点的路上）一个或多个顶点输入。 因此，如果顶点是节点，并且边缘取决于关系，则查找将受给定节点集影响的所有节点。

如果没有写出自己的算法有多难？

Answer 1

这是我用来完成给定顶点上的前任搜索：

IBidirectionalGraph> CreateGraph(int vertexCount) { BidirectionalGraph> graph = new BidirectionalGraph>(true); for (int i = 0; i < vertexCount; i++) graph.AddVertex(i); for (int i = 1; i < vertexCount; i++) graph.AddEdge(new Edge(i - 1, i)); return graph; } static public void Main() { IBidirectionalGraph> graph = CreateGraph(5); var dfs = new DepthFirstSearchAlgorithm>(graph); var observer = new VertexPredecessorRecorderObserver>(); using (observer.Attach(dfs)) // attach, detach to dfs events dfs.Compute(); int vertexToFind = 3; IEnumerable> edges; if (observer.TryGetPath(vertexToFind, out edges)) { Console.WriteLine("To get to vertex '" + vertexToFind + "', take the following edges:"); foreach (IEdge edge in edges) Console.WriteLine(edge.Source + " -> " + edge.Target); } } 

请注意，如果您事先知道了root，则可以在dfs.Compute()方法中指定它（即dfs.Compute(0) ）。

-Doug

Answer 2

我使用了Doug的答案，发现如果一个顶点有多个父级，他的解决方案只提供一个父级。 我不知道为什么。

所以，我创建了自己的版本，如下所示：

  public IEnumerable GetParents(T vertexToFind) { IEnumerable parents = null; if (this.graph.Edges != null) { parents = this.graph .Edges .Where(x => x.Target.Equals(vertexToFind)) .Select(x => x.Source); } return parents; } 

Answer 3

您需要维护反转图形，或者在图形上创建一个反转每个边缘的包装器。 QuickGraph有ReversedBidirectionalGraph类，它是一个专门用于它的包装器，但由于通用类型不兼容，它似乎不适用于算法类。 我必须创建自己的包装类：

 class ReversedBidirectionalGraphWrapper : IVertexListGraph where TEdge : IEdge { private BidirectionalGraph _originalGraph; public IEnumerable OutEdges(TVertex v) { foreach (var e in _graph.InEdges(v)) { yield return (TEdge)Convert.ChangeType(new Edge(e.Target, e.Source), typeof(TEdge)); } } //...implement the rest of the interface members using the same trick } 

然后在此包装器上运行DFS或BFS：

 var w = new ReversedBidirectionalGraphWrapper>(graph); var result = new List(); var alg = new DepthFirstSearchAlgorithm>(w); alg.TreeEdge += e => result.Add(e.Target); alg.Compute(node); 

Doug的答案不正确，因为DFS只会访问下游子图。 前任观察员没有帮助。