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