.net - 在 .NET 中表示有向无环图的结构是什么？

Question

我正在考虑将DAG表示为Dictionary(Of Integer, List(Of Integer)) 其中键将是顶点 ID，并且列表将包含沿边缘的所有目标顶点。

稍后我将使用此结构来：

导出可能的上升和下降路径列表

导出可能的下一个路径和可能的源路径的列表

导出叶节点列表

验证顶点之间的提议边

拓扑排序顶点

我的方法有问题吗？你过去是怎么做到的？谢谢

编辑
我的方法的一个问题是找到顶点的源路径是一项昂贵的操作，因为它需要对整个字典进行迭代。也许让一个DAGVertex物体暴露出来Targets并符合我的兴趣Sources

Answer 1

您可以将图形表示为两个字典——一个用于传入边，一个用于传出边。O(V + E)这将使修改图形和内存消耗的时间增加一倍，但降低了从to获取到达某个顶点的边列表的时间复杂度O(1)。

获取叶节点列表可以类似地完成——只需要一个当前叶节点列表（或Dictionary(Of Integer, Boolean)）。每当它成为叶节点时添加一个节点，如果它不再是叶节点，则将其删除。

Answer 2

我相信我会为我的节点创建实体，然后在我的方法中使用 OOP。

如果您的要求永远不会改变并且您对此完全确定，也许您的方法是可以的，但是如果您可能有需求更改，例如为节点和另一个节点之间的每条路径分配“权重”，我相信这可能会很困难去做吧。（会通过做类似的事情来解决它；

Dictionary<Int32, List<Int32, Dictionary<Int32, Int32>>

？？？）

我想我的课看起来有点像这样；

public class GraphNode
{
    private Int32 value;
    public Int32 Value
    {
        get { return this.value; }
    }

    private List<GraphNode> siblings;
    public ReadOnlyCollection<GraphNode> Siblings
    {
        get { return new ReadOnlyCollection<GraphNode>(siblings); }
    }

    public void AddSibling(GraphNode node)
    {
        if (this == node)
            throw new Exception("Can't assing a node to itself as a sibling");

        if (this.siblings.Contains(node))
            throw new Exception("This node is already contained in the siblings list");

        this.siblings.Add(node);
    }

    public GraphNode(Int32 value)
    {
        this.value = value;
        this.siblings = new List<GraphNode>();
    }
}