在C ++图形结构中高效地表示边

我正计划在C ++中表示一个相当大，稀疏，无向的图结构。 这将是10000个顶点的数量级，每个顶点的度数大约为10。

我已经阅读了关于表示图形作为相邻矩阵或列表的一些背景，但其中的更近似于我想要做的事。 在我的场景中：

图形中的每条边都会附加一些属性（数值）

在初始图形创建之后，边缘可以被删除，但从未创建

顶点永远不会被创建或删除

图上的主要查询操作将是对于边E的查找，以及关于哪些其他边连接到边。 这相当于找到连接到E的每一端的顶点的边。

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

我相信邻接列表会减少所需的操作，但由于我包含每个边缘的参数而看起来不合适 - 也就是说，因为邻接列表存储每个

有没有更好的方式来存储我的数据，以便这些查询操作更快，并且我可以存储每个边缘的参数？ 我不想开始实施一些不正确的做法。

---

在这里，我没有看到通常的面向对象方法的问题。 让您的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的前一个位置。 定时去除。 线性时间（以操作结果的大小）枚举所有相邻边到特定边。 听起来不错。

---

像这样的东西看起来似乎合理吗？ 这存储边缘邻接关系：

#include <vector>
#include <map>

typedef int vertex;

struct edge
{
    vertex a,b;
    // other data
};

bool operator< (const edge &a, const edge &b)
{
    unsigned long long ahash = a.a;
    ahash << 32;
    ahash |= a.b;
    unsigned long long bhash = b.a;
    bhash << 32;
    bhash |= b.b;
    return ahash < bhash;
}

// support for your query operation
typedef std::map<edge, std::vector<edge &> > edge_adjacency;

看起来你有点想将边缘映射到顶点，然后使用相当标准的东西。

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

上一篇: Efficient representation of edges in a C++ graph structure

下一篇: using both directed and undirected edges