Java中的图/数据结构算法

Question

我很乐意为您进行翻译。以下是需要翻译的内容：我一直在处理一个问题，我有一个包含两列的 CSV 文件，我们可以称之为“朋友”字段。这两列都包含从 A 到 Z 的字母。例如：

A B
B C
A E
D F
E F

每一行有两个不同的字母（一行内不重复）。A是B的朋友，C是D的朋友，以此类推。如果A与B交谈，而B又与C交谈，则B和C会成为熟人。熟人指有共同朋友的人。我需要找出谁拥有更多的熟人？

我已经尝试了两种不同的方法，一种使用不同的数据结构，比如哈希映射、数组列表、栈等，另一种使用图论（JGraphT库）。但是，如果我使用数据结构，我卡在了逻辑上；如果我使用图论，我卡在了遍历图上。

我的问题如下：

1. 数据结构或图形哪种方法更好？还是有其他更好的方法/逻辑/算法吗？ 2. 有人知道如何在JgraphT库中遍历图形。我不能做到这一点，因为它们对该库的文档非常有限。

请，任何帮助都将不胜感激。

- Pankaj Gadge

Answer 1

通常情况下，HashMap是最快速和易于使用的。我建议您使用它们而不是任何自定义库，除非您确定某个库可以轻松地完成您需要的工作，并且编写代码需要很长时间。

在您的情况下，您只需将每个人用作键，他的朋友列表作为指向的对象即可。解析您的.csv文件并相应地填充HashMap将解决您的问题，正如先前的评论所指出的那样。

- chiffa

Answer 2

你可以先创建一个哈希表，将每个字母映射到它的朋友集合上，例如 A 映射到 { B }，B 映射到 { C }，如果 Z 有两个朋友 Y 和 W，则 Z 映射到 { Y, W }。这是一个从字母到字母集合的哈希映射。

要计算熟人，遍历哈希表。当你在条目 A -> { B, C, F } 时，通过内部循环遍历集合 B、C、F。将它们的朋友（三个集合）收集到一个单一的集合中（只需将元素插入临时集合中），如果找到了 A，则从该集合中删除 A。那个集合的大小就是 A 的熟人数量。反复执行此操作。

- Antti Huima