从圈里找一小群朋友?

有没有更好的方法来解决这个问题?

更好的方法是使用 disjoint-set data structure :

• 首先,将“朋友组”计算为不相交的集合数据结构:
  • 初始化一个不相交的集合数据结构,其中集合的元素将是房间中的人员。
  • 为每个人 磷 房间里:
    • 呼叫 马克塞特 ( 磷 )初始化仅包含此人的“朋友组”。
  • 为每一个直接的友谊 磷 _一 艾斯 磷 _二 :
    • 呼叫 联合 ( 磷 _一 , 磷 _二 )统一包含 磷 _一 与包含 磷 _二 .
• 接下来,计算“朋友组”的大小作为地图:
  • 初始化一个地图,其中键将是房间中的一些人(即他们各自的“朋友组”的代表),值将是数字(即各种“朋友组”的大小)。
  • 为每个人 磷 _一 房间里:
    • 呼叫 发现 ( 磷 _一 )找到代表 磷 _二 在那个人的“朋友组”中。
    • 如果映射尚未包含键的值 磷 _二 ,插入该键的值0。
    • 增加键的值 磷 _二 .
• 最后,计算结果:
  • 将结果初始化为较大的值,例如房间中的人数。
  • 对于地图中的每个值(=一个“朋友组”的大小):
    • 如果该值小于结果,则将结果设置为等于该值。
  • 返回结果。

顺便说一下,你正在执行的操作的技术名称是 transitive closure “是朋友”关系是“直接是朋友”关系的传递闭包。(然而,维基百科文章中描述的算法并不适合你的问题,因为它们没有利用你的关系 symmetric )

这是一些代码,我出于好奇写下了你的问题。我对图形不太了解,但它使用递归,就像您所要求的那样。

基本上,你通过输入,为每个人,你创建一个 ArrayList<Integer> . 在这个数组中,是那个人的直接朋友。例如,对于 1: {6}, for 2: {7, 6}, for 3: {8, 5} . 然后,得到 全部的 第二个人的朋友,你创造了一个整体 数组列表<integer> 将第7和第6个人的数组组合在一起(不包括重复的数组)。因此,递归可以用函数 getAllFriends(Integer person) 必须归还 getAllFriends(Integer person2) 也为了那个人的直接朋友。

因此,代码可能看起来像这样:

public class Test  {
        public static void main(String[] args) throws Exception {
            String input = "1<->6\n" +
            "2<->7\n" +
            "3<->8\n" +
            "4<->9\n" +
            "2<->6\n" +
            "3<->5";

            HashMap<Integer, ArrayList<Integer>> friends = processInput(input);  //getting data from the input string and storing it in a structured way
            System.out.println(getAllFriends(1, friends, new ArrayList<Integer>(){{add(1);}}));  //output: [1, 6, 2, 7]. Double brackets create an anonymous inner class, you add to the result the id of a person whose friends you're collecting
            }

        public static HashMap<Integer, ArrayList<Integer>> processInput(String input) throws Exception  {
            HashMap<Integer, ArrayList<Integer>> result = new HashMap<>();

            BufferedReader bufReader = new BufferedReader(new StringReader(input));
            String line=null;
            while( (line=bufReader.readLine()) != null )
            {
                Integer personLeft =  Integer.valueOf(line.substring(0, line.indexOf("<")));
                Integer personRight =Integer.valueOf(line.substring(line.indexOf(">")+1, line.length()));

                System.out.println(personLeft + ": " + personRight);

                if (!result.containsKey(personLeft))  {
                    result.put(personLeft, new ArrayList<Integer>());
                }

                result.get(personLeft).add(personRight);

                if (!result.containsKey(personRight))  {
                    result.put(personRight, new ArrayList<Integer>());
                }

                result.get(personRight).add(personLeft);
            }


            return result;

        }

        public static ArrayList<Integer>  getAllFriends(Integer person, HashMap<Integer, ArrayList<Integer>> friends, ArrayList<Integer> result)  {
            for (Integer personFriend: friends.get(person))  {
                    if (!result.contains(personFriend))  {
                        result.add(personFriend);  //add a person, if it wasn't added before
                        getAllFriends(personFriend, friends, result);  //check out that person's friends
                    }
            }

            return result;
        }
}