c++ - 我可以使用什么样的数据结构来处理这种方式

Question

该示例被简化为一个玩具示例，但我将处理 1000 个节点。

我们有 5 个节点

t1
t2
a0
a1

t1 connects to a0 and a3
t2 connects to a0, a1, a2 and a3
a0 connects to a1
a1 connects to a0, t2

我的最终目标是制作一个程序，该程序将使用图形库绘制节点之间以及节点之间的连接。

我可以使用什么样的数据结构。我的第一个想法是使用链表，但我认为这不适用于这种情况，因为该数据结构仅在每个节点之间使用一个连接。

标签： c++arraysarraylistdata-structures

Answer 1

您的数据结构是图形。根据连接数与节点数的比率，您应该选择一个能够提供足够运行时效率并节省内存的表示：

• 如果比率低（连接相对较少的节点很多），则图是稀疏的。表示稀疏图的一个很好的数据结构是邻接表。
• 如果比率很高（很多节点，每个节点都连接到其他节点的四分之一），则图是密集的。密集图的一个很好的表示是邻接矩阵。