c# - 将 DataStructure 用于 Graph（自己的实现）

Question

我将用 C# 编写自己的 Graph 结构（我知道这样的存在，但我想练习 + 我需要自定义方法）。这个想法很简单：

1. 该类Graph<T>将有一组GraphNode<T>对象，代表节点
2. 每个节点将有一组GraphNode<T>表示节点的对象，它连接到这些节点（定向图）。

我的问题很简单：如果我想快速遍历集合应该使用什么数据结构GraphNode<T>？快速添加/删除是 +，但不是主要目标。

Answer 1

如果您期望节点数量相对较少（少于十万），则可以使用邻接矩阵（对于较大数量的节点，您可以使用按位运算符；这也取决于您的图是否加权）。这在插入/删除时会非常慢。

对于快速图遍历，邻居节点列表将很有用，因为它可以非常快速地遍历。此外，这种方法将允许并行化遍历，从而提高性能。这种方法可能是您正在寻找的最佳方法。

我会去List<GraphNode<T>>存储邻居。对于具有许多节点的加权图 aConcurrentDictionary<GraphNode<T>, double>应该表现良好。