具有恒定时间复杂度的无向图边的数据结构

2018-06-18 13:49:56

我有一个无向图，其中节点存储在一个平面阵列中。现在我正在寻找边缘的数据结构。它应该具有恒定的时间复杂度，以获得给定节点的所有边。边缘包含两个节点索引和附加信息，如权重。

我看到的唯一方法是复制数据，一个按左节点排序，另一个按右节点排序。

vector<vector<int>> left, right;

但我想防止重复边缘。

这听起来像你只是想要一个邻接表的表示。

在这种表示中，每个节点将存储其所有连接边的列表。

对于无向图，可以让每个端点都存储边。

没有一种真正的方法可以在没有重复的情况下持续获得节点的连接边。但是，您可以将指针，引用或唯一ID（例如，可以是边缘数组中的索引）存储到实际边缘，从而避免需要实际拥有2个副本。

制作矢量矢量。

每个节点都有一个它拥有的所有节点的向量。

您应该在创建图表时创建它。

链接地址: http://www.djcxy.com/p/52377.html