适合图的数据结构(自己实现)
本文关键字：自己 实现 数据结构 | 更新日期: 2023-09-27 18:15:05
我将在c#中编写自己的图形结构(我知道这样的存在，但我想实践+我需要自定义方法)。思路很简单:
-
Graph<T>类将有一组GraphNode<T>对象，代表节点 - 每个节点都有一组代表节点的
GraphNode<T>对象，与之相连(有向图)。
我的问题很简单:如果我想要快速遍历GraphNode<T>的集合，我应该使用什么数据结构?快速添加/删除是+，但不是主要目标。
如果你期望的节点数量相对较少(少于10万个)，你可以使用邻接矩阵(对于更大数量的节点，你可以使用位运算符;这也取决于你的图表是否被加权)。这将在插入/删除时非常慢。
对于快速图遍历，一个邻居节点列表将是有用的，因为它可以非常快速地遍历。此外，这种方法将允许并行遍历，这将提高性能。这种方法可能是您正在寻找的最佳方法。
我会用List<GraphNode<T>>来存储邻居。对于一个有许多节点的加权图，ConcurrentDictionary<GraphNode<T>, double>应该表现得很好。