我有一个无向图，其中节点存储在平面数组中。现在，我正在寻找边缘的数据结构。为了获得给定节点的所有边缘，它应该具有恒定的时间复杂度。一条边包含两个节点索引和其他信息，例如权重。
我看到的唯一方法是复制数据，一种按左节点排序，另一种按右节点排序。
vector<vector<int>> left, right;
但我想避免重复边缘。
最佳答案
听起来您只需要adjacency list表示形式。
在此表示中，每个节点将存储其所有连接边的列表。
对于无向图，可以让每个端点都存储边。
确实没有一种方法可以在恒定时间内不重复地获取节点的连接边。但是您可以只存储指向实际边缘的指针，引用或唯一ID（例如，可以是边缘数组中的索引），从而无需实际浮动2个副本。
关于c++ - 具有恒定时间复杂度的无向图边的数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20869292/