提问人：user5965026 提问时间：4/29/2020 最后编辑：user5965026 更新时间：4/29/2020 访问量：187
用于形成嵌套邻居邻接列表的算法
Algorithm for forming adjacency list with nested neighbors
问：
当给定同义词列表时，我很难想出一个好的算法来形成邻接列表。
同义词列表以向量的向量形式提供。内部向量的大小为 2，由 2 个同义词组成。
例如，
std::vector<std::vector<std::string>> synonyms{{"joy", "happy"}, {"happy",
"ecstatic"}, {"cheerful, ecstatic"}, {"big", "giant"}, {"giant", "gigantic"}};
所以这里我们有 2 组同义词： 和{joy, happy, ecstatic, cheerful}{big, giant, gigantic}
我想使用 .该值为 a，因为需要对邻居进行排序。或者，该值可以是一个向量，然后我们最终会对向量进行排序。
在给定边缘的情况下，使此邻接列表的最佳方法是什么？std::unordered_map<std::string, std::set<std::string>>set
对于这个邻接列表，我希望每个单词都有一个条目。所以在上面的例子中，我将有 7 个条目。对于每个条目，我想将其映射到它同义的所有单词。像这样：
{happy} -> {cheerful, ecstatic, joy}
{joy} -> {cheerful, ecstatic, happy}
{ecstatic} -> {cheerful, happy, joy}
{cheerful} -> {ecstatic, happy, joy}
{giant} -> {big, gigantic}
{big} -> {giant, gigantic}
{gigantic} -> {big, giant}
答：
0赞
JohnFilleau
4/29/2020
#1
假设两个孤立的单词邻域 Na 和 Nb。邻域中的每个单词都知道邻域中的所有其他单词（同义词）。然后，我们指定来自 Na 的单词 called 和来自 Nb 的单词 called 被声明为同义词。我们必须将 和 的每个邻居（即 Na 中的每个单词）和 的每个邻居（即 Nb 中的每个单词）添加到其邻居（同义词）列表中。我们必须让 Nb 中的每个单词将 Na 中的每个单词添加到其邻居（同义词）列表中。WaWbWaWaWbWb
在此操作结束时，所有单词都知道新组合邻域中的所有其他单词，这使得该新邻域成为上述算法的另一次迭代的有效输入。
尚未添加同义词的单个单词是 1 的邻域，这使其成为算法的有效输入。
不要想着组合单词。考虑合并邻域。每个单词都映射到其完整的邻域以开始。这使得将社区塞在一起变得更加容易。稍后，我们可以将每个单词从其自己的邻域中删除。
std::unordered_map<std::string, std::set<std::string>> al;
for (auto const & syns : synonyms)
for (auto const & word : syns)
{
al[word].insert(word);
for (auto const & syn : syns)
{
al[syn].insert(syn);
if (word != syn)
{
// add the entire neighborhood of word to
// the entire neighborhood of syn, and vice versa
for (auto const & neighbor_word : al[word])
for (auto const & neighbor_syn : al[syn])
{
al[child_word].insert(child_syn);
al[child_syn].insert(child_word);
}
}
}
}
// remove each word's mapping to itself as a synonym:
for (auto & words : al)
words.second.erase(words.first);
太乱了，我不想评估复杂性，但要完成工作。我认为？
等待同行评审...
评论
vector<vector<string>>