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

Question

我计划使用C++来表示一个相当大、稀疏和无向的图结构。该图将包含10,000个以上的顶点，每个顶点的度数约为10。

我已经阅读了有关使用邻接矩阵或邻接表来表示图形的一些背景资料，但它们似乎都不适合我的需求。在我的情况下：

• 图中的每条边都有一些属性（数值）附加到上面
• 在初始图形创建后，可以删除边，但永远不能创建新的边
• 顶点永远不会被创建或删除
• 主要的图查询操作将是查找与边E连接的其他边。这相当于找到E两端的顶点连接的边。

正是最后一点使得邻接矩阵似乎不太合适。据我所见，每次查询都需要2*N个操作，其中N是图中节点的数量。

我相信，邻接表可以减少所需的操作，但由于我正在每个边上包含参数，它看起来并不适合——即因为邻接表存储每个

有没有更好的方法来存储我的数据，使得这些查询操作更快，并且我可以存储每个带有参数的边？我不想开始实现错误的方法。

- Bill Cheatham

---

邻接表可以，你可以将数据与边一起附加。邻接矩阵不行，除非你有大量可用的内存（接近100 MB），而总共只有10^5条边。 - nhahtdh

好的，谢谢。但是我该如何处理邻接表中的重复呢？每条边将在节点i的行和节点j的行中各表示一次。 - Bill Cheatham

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的前一个位置。常数时间删除。枚举特定边所有相邻边需要线性时间（与操作结果的大小成正比）。听起来不错。

- bitmask

---

太棒了，看起来这似乎符合所有要求。不过我还不太理解你关于删除一条边的评论。你是指从 Vertex<V,E>::edges 中删除一条边时，将它在向量中的位置替换为向量末尾的边（可能还要更新该替换边的一个vertices条目）吗？ - Bill Cheatham

@BillCheatham：是的，完全正确。否则你的向量中就会有未定义的间隙，这是相当棘手的问题。但由于事故边缘的顺序无关紧要，你只需将“back”元素移动到现在的空槽中，并将向量缩小一个即可。 - bitmask

好的，我现在快要完成这个系统了。我只有一个问题，就是如何存储我的“边缘”和“顶点”元素。我尝试使用向量，但每次删除边缘都会使向量中其他边缘的指针失效。数组不允许有效地删除元素，而列表则不允许随机访问单个边缘。 - Bill Cheatham

Answer 2

这样的想法听起来可行吗？它存储边缘相邻性：

#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;

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

- Nathan Andrew Mullenax