一个未知大小的无向图的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的情况下，您可以轻松获得所有相邻节点的迭代器。

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