C++图结构中边的有效表示

Question

我计划在C++中表示一个相当大,稀疏,无向图形结构.这将是10,000多个顶点的量级,每个顶点具有大约10的度数.

我已经阅读了一些关于将图表表示为邻接矩阵或列表的背景,但是它们中的较近似乎适合我想要做的事情.在我的场景中:

• 图中的每条边都会附加一些属性(数值)
• 创建初始图形后,可以删除边,但从不创建边
• 永远不会创建或删除顶点
• 图上的主查询操作将是对边E的查找,以及与其连接的其他边.这相当于找到连接到E的每一端的顶点的边.

这是最后一点,使邻接矩阵看起来不合适.据我所知,每个查询都需要2*N个操作,其中N是图中的节点数.

我相信邻接列表会减少所需的操作,但似乎不合适,因为我在每个边缘包含的参数 - 即因为邻接列表存储每个

有没有更好的方法来存储我的数据,以便这些查询操作更快,我可以存储每个边缘及其参数？我不想开始实现一些不正确的方法.

Answer 1

在这里,我没有看到通常的面向对象方法的问题.您的Edge<V,E>和Vertex<V,E>类型在哪里V是顶点存储的内容,E是边存储的内容.每个边都有两个对其各自顶点的引用和两个索引,它们表示在相应顶点的哪个槽中查找该边:

template <typename V, typename E>
class Edge {
  struct Incidence {
    size_t index;
    Vertex<V,E>& v;
  };
  std::array<Incidence,2> vertices;
  E content;
};

template <typename V, typename E>
class Vertex {
  std::vector<Edge<V,E>*> edges;
};

如果移除边缘e,则Vertex<V,E>::edges移动back到前一个位置的位置e.恒定时间删除.用于枚举特定边的所有相邻边的线性时间(在操作结果的大小中).听起来不错.