QuickGraph - 是否有算法可以找到一组顶点的所有父级（直到根顶点）

Question

在 QuickGraph 中 - 是否有算法可以查找一组顶点的所有父级（直到根顶点）。换句话说，所有顶点的下方某处（在通往叶节点的路上）都有一个或多个顶点输入。因此，如果顶点是节点，边是依赖关系，则找到将受给定节点集影响的所有节点。

如果不是的话，编写自己的算法有多难？

Answer 1

这是我用来完成给定顶点的前驱搜索的方法：

IBidirectionalGraph<int, IEdge<int>> CreateGraph(int vertexCount)
{
    BidirectionalGraph<int, IEdge<int>> graph = new BidirectionalGraph<int, IEdge<int>>(true);
    for (int i = 0; i < vertexCount; i++)
        graph.AddVertex(i);

    for (int i = 1; i < vertexCount; i++)
        graph.AddEdge(new Edge<int>(i - 1, i));

    return graph;
}

static public void Main()
{
    IBidirectionalGraph<int, IEdge<int>> graph = CreateGraph(5);

    var dfs = new DepthFirstSearchAlgorithm<int, IEdge<int>>(graph);            
    var observer = new VertexPredecessorRecorderObserver<int, IEdge<int>>();

    using (observer.Attach(dfs)) // attach, detach to dfs events
        dfs.Compute();

    int vertexToFind = 3;
    IEnumerable<IEdge<int>> edges;
    if (observer.TryGetPath(vertexToFind, out edges))
    {
        Console.WriteLine("To get to vertex '" + vertexToFind + "', take the following edges:");
        foreach (IEdge<int> edge in edges)
            Console.WriteLine(edge.Source + " -> " + edge.Target);
    }
}

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

-道格