2

我曾多次为几位雇主有理由实现我自己的图形数据结构。为了获得完全的访问灵活性，我经常需要使用两个类来实现它，一个Node类和一个Edge类。

然后一个节点将有一组传出边（可能还有传入边），并且一个边将有一个源和一个接收器（都是指向节点的托管指针）。这些图经常有循环。

我的问题是：在此类图形数据结构中管理内存的最佳方法是什么，尤其是在转换和变异图形时？由于循环的存在，它们不适合引用计数（即使您尝试使用弱指针，通常也不清楚循环的位置以及弱链接的放置位置）。

在我的各种实现中，我经常跟踪所有分配的节点和边，与图表以及图表的入口点列表分开。然后我实现了一个简单的垃圾收集器。定期应用各种图形转换（包括取消链接一些节点/边）后，我运行 gc，其中涉及：

  1. 从入口点节点开始，并将通过图形从那里可到达的所有节点和边标记为活动的（通过 BFS/DFS）。
  2. 迭代整个集合中的所有节点和边，并删除上一步中未标记的任何节点和边。

这很好用（并且是标记/扫描的简单实现）。但它总是看起来有点笨拙。有没有人对此问题有任何见解，或更好的替代解决方案？

4

1 回答 1

0

当您有有限图时，不要将它们表示为指针结构。相反，使用

  • 一个边列表（vector, list, 不管）和一个顶点列表，或者
  • 顶点到索引的映射（map或）和表示顶点和是否连接unordered_map的布尔值（或加权图的浮点数）矩阵（二维数组） 。ij

前一种表示称为邻接表，后一种称为邻接矩阵。使用哪一个取决于您拥有的图表和您要执行的操作。两者在内存管理方面都更简单，并且通常比指针结构更高效，因为它们占用的内存更少并且倾向于保留引用的局部性。

于 2012-07-09T22:25:01.770 回答