c++ - 在 C++ 中实现图形的最佳方法？

Question

我正在寻求实现一个恒定的、无序的、未加权的、稀疏的图（即边不移动）。但是，我会做很多顶点交换操作，从而改变顶点的顺序。

例如，一种方法是使用 unordered_sets 的向量 + 邻接表结构：

0: 1 2 3
1: 0 2
2: 0 1
3: 0

交换 0 和 3：

0: 3
1: 3 2
2: 3 1
3: 1 2 0

C++ 中最好的实现是什么？

Answer 1

Look into Boost Graph Library. It will probably work for your needs, but if it doesn't, it's documentation may be a good starting point to learn about the subject, before you start trying to roll your own.

Edit: If you're expecting to work with sparse graphs, the adjacency list version is probably the implementation you want to look into first. Note that you can tweak the performance characteristics of a boost adjacency_list graph by changing the underlying data structures used to implement it (via template argument).

Edit: In regards to the vertex swapping you're describing, probably the easiest way to do this is to set up a vertex type where the vertex can remain in place, but its properties can easily be swapped with another. The Bundled Properties mechanism is one way to implement this.

Answer 2

boost::graph perhaps.

It has several implementations, and you can specify multiple parameters per vertex. Further investigation is left as an exercise for the student.