4

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

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

4

3 回答 3

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)）。

-道格

于 2010-05-03T18:59:12.943 回答
1

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

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

    public IEnumerable<T> GetParents(T vertexToFind)
    {
        IEnumerable<T> parents = null;

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

        return parents;
    }
于 2012-07-20T19:19:09.363 回答
1

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

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

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

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

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

于 2016-08-12T18:53:48.243 回答