java - 在图中找到 'connected components'

Question

我正在使用 HashMap <String,ArrayList<String>> 构建同义词库保存单词及其同义词(需要此数据结构)。

为了分配的目的，同义关系被认为是传递的。 (我们可以把词库想象成一个图表)。
我想要完成的是在一个文本文件中打印这个图，每行都有一个连接的组件。换句话说，所有可以合并为同义词的单词都应该放在一行中。

public void save() {
    try {
        FileWriter fw = new FileWriter(defaultDefinitionFile);
        BufferedWriter out = new BufferedWriter(fw);
        Set<String> keys = thesaurus.keySet();
        Iterator<String> ite = keys.iterator();
        while (ite.hasNext()) {
            String key = ite.next();
            out.write(key);
            ArrayList<String> synonyms = thesaurus.get(key);
            Iterator<String> i = synonyms.iterator();
            while (i.hasNext()) {
                String syn = i.next();
                out.write(","+syn);
                keys.remove(syn);
            }
            out.write("\r\n");
        }
        out.close();
        fw.close();
    }
    catch (Exception e) {
        System.out.println("Error writing to file");
        e.printStackTrace();
    }
}

这就是我想象它发生的方式:

打印一个单词及其每个同义词，然后从数据结构中删除这些同义词，这样我们就没有重复的行。

问题当然是我在迭代哈希图的内容时无法删除任何内容。

我缺少任何替代方法吗？

附言我一直保留“图表”的隐喻只是因为我需要标题 Eloquent 而简洁。我知道这个比喻的用处有限。

Answer 1

您可以将打印的单词存储在 Set 中。 ，然后只处理尚未在集合中的单词。

旁注:尽管确实可以将其视为图形问题，但您的代码并未将其视为这样。如果我们将其视为图形问题，那么我们就不会假设每个单词的所有同义词都列在相应的 ArrayList 中。 ，因此需要计算对称和传递闭包。只有这样我们才能提取等价类。

(实际上，同义词关系不是及物的，我知道。)