c++ - 未知大小的无向图的 C++ 数据结构

Question

我正在尝试制作一个程序来探索未知大小的无向图并在运行时构建邻接列表。通常我会做一个set<set<String>>（房间由一个字符串标识），但有人告诉我这在 C++ 中是不稳定的。什么是更好的数据结构？

Answer 1

这取决于您以后要如何查询信息。

我可以提出两种选择：

using namespace std;
set< pair<string,string> >

或者

using namespace std;
multimap<string,string>

在第一种情况下set，您可以检查两个节点是否已连接，但您需要知道两个节点（A 和 B）才能运行查询。在第二种情况下multimap，给定节点 A，您可以轻松获得具有所有相邻节点的迭代器。

您将需要插入对两次或使用一些规则，例如始终按字典顺序添加边。