c++ - 与嵌套邻居形成邻接表的算法

Question

当给定同义词列表时，我很难想出一种形成邻接表的好的算法。

同义词列表作为 vector 的 vector 提供。内部 vector 的大小为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}
我想使用 std::unordered_map<std::string, std::set<std::string>>从边缘列表创建邻接列表。该值是 set，因为需要对邻居进行排序。或者，该值可以是一个 vector ，然后我们将对 vector 进行最后排序。
给定边缘，使邻接表最好的方法是什么？

对于此邻接表，我想要每个单词一个条目。因此，在上面的示例中，我将有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}

Answer 1

假设两个孤立的单词邻域 Na 和 Nb 。邻居中的每个单词都知道邻居中的所有其他单词(同义词)。然后，我们指定 Na 中的单词Wa和 Nb 中的单词Wb声明为同义词。我们必须让Wa和Wa的每个邻居(即的每个单词Na )将Wb和Wb的每个邻居(即 Nb )的每个邻居添加到其邻居列表(同义词)。并且我们必须让 Nb 中的每个单词将 Na 中的每个单词添加到其邻居列表(同义词)中。

在该操作结束时，所有单词都知道新组合邻域中的所有其他单词，这使该新邻域成为上述算法的另一次迭代的有效输入。

尚未添加同义词的单个单词的邻域为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);

乱七八糟，我不想评估复杂性，但可以完成工作。我认为？

待审核的同行...