BFS实现查找连接组件时间过长

Question

这是我问here的问题的延续。
鉴于节点（雇员）总数和邻接表（员工之间的友谊），我需要找到所有连接的组件
。下面是我的代码 -

public class Main { 
     static HashMap<String, Set<String>> friendShips; 

     public static void main(String[] args) throws IOException { 
      BufferedReader in= new BufferedReader(new InputStreamReader(System.in)); 

       String dataLine = in.readLine(); 
       String[] lineParts = dataLine.split(" "); 
       int employeeCount = Integer.parseInt(lineParts[0]); 
       int friendShipCount = Integer.parseInt(lineParts[1]); 
       friendShips = new HashMap<String, Set<String>>(); 
       for (int i = 0; i < friendShipCount; i++) { 
        String friendShipLine = in.readLine(); 
        String[] friendParts = friendShipLine.split(" "); 
        mapFriends(friendParts[0], friendParts[1], friendShips); 
        mapFriends(friendParts[1], friendParts[0], friendShips); 
       } 
       Set<String> employees = new HashSet<String>(); 
       for (int i = 1; i <= employeeCount; i++) { 
        employees.add(Integer.toString(i)); 
       } 
       Vector<Set<String>> friendBuckets = bucketizeEmployees(employees); 
       System.out.println(friendBuckets.size()); 
     } 

     public static void mapFriends(String friendA, String friendB, Map<String, Set<String>> friendsShipMap) { 
      if (friendsShipMap.containsKey(friendA)) { 
       friendsShipMap.get(friendA).add(friendB); 
      } else { 
       Set<String> friends = new HashSet<String>(); 
       friends.add(friendB); 
       friendsShipMap.put(friendA, friends); 
      } 
     } 

     public static Vector<Set<String>> bucketizeEmployees(Set<String> employees) { 
      Vector<Set<String>> friendBuckets = new Vector<Set<String>>(); 
      while (!employees.isEmpty()) { 
       String employee = getHeadElement(employees); 
       Set<String> connectedEmployeesBucket = getConnectedFriends(employee); 
       friendBuckets.add(connectedEmployeesBucket); 
       employees.removeAll(connectedEmployeesBucket); 
      } 
      return friendBuckets; 
     } 

     private static Set<String> getConnectedFriends(String friend) { 
      Set<String> connectedFriends = new HashSet<String>(); 
      connectedFriends.add(friend); 
      Set<String> queuedFriends = new LinkedHashSet<String>(); 
      if (friendShips.get(friend) != null) { 
       queuedFriends.addAll(friendShips.get(friend)); 
      } 
      while (!queuedFriends.isEmpty()) { 
       String poppedFriend = getHeadElement(queuedFriends); 
       connectedFriends.add(poppedFriend); 
       if (friendShips.containsKey(poppedFriend)) 
        for (String directFriend : friendShips.get(poppedFriend)) { 
         if (!connectedFriends.contains(directFriend) && !queuedFriends.contains(directFriend)) { 
          queuedFriends.add(directFriend); 
         } 
        } 
      } 
      return connectedFriends; 
     } 

     private static String getHeadElement(Set<String> setFriends) { 
      Iterator<String> iter = setFriends.iterator(); 
      String head = iter.next(); 
      iter.remove(); 
      return head; 
     } 
    } 

我曾尝试使用下面的脚本测试我的代码，其结果我消耗为sdtIn -

#!/bin/bash 
echo "100000 100000" 
for i in {1..100000} 
do 
    r1=$(($RANDOM % 100000)) 
    r2=$(($RANDOM % 100000)) 
    echo "$r1 $r2" 
    done 

，而我是能够验证（为小事输入），我的答案是正确的，当我尝试与上面的脚本巨大的投入，我看到运行需要很长时间（〜20s）。
任何我可以在我的实施中做得更好的东西？

Answer 1

避免使用同步的类Vector。改为ArrayList。 如果你找到一种方法来aovid字符串和使用Integer，将是一个优势。 （例如，userId而不是userName