優化此代碼以查找連接的組件？

Question

我有無向圖，我需要找到圖的連接組件的數量。我將圖形表示爲Map<Integer, ArrayList<Integer>> map（節點：連接節點列表）。然後我通過該地圖並計算連接組件

int countComponents() { 
    for (Integer u : map.keySet()) { //all nodes 
     if (visited[u] == false) { 
      visited[u] = true; 
      components++; 
      dfs(u); 
     } 
    } 
    return components; 
} 

void dfs(int u) { 
    for (Integer v : map.get(u)) { //v is node connected to u 
     if (visited[v] == false) { 
      visited[v] = true; 
      dfs(v); 
     } 
    } 
} 

但是我需要更高效的算法。也許最好使用圖的另一種表示形式，或者有另外一種方法來查找連接組件的數量？

Answer 1

如果您沒有關於圖的連通組件的任何先驗知識，那麼您在這裏得到的算法速度就會快得多。 （DFS以線性時間運行。）如果您想加快速度，除非您有關於圖形結構的其他信息，否則您可能只能通過一個常數來做到這一點。

我建議看看不相交集森林數據結構，這是一個非常快速的數據結構，用於維護連接的組件。它的速度比DFS慢，但恆定因素非常低，您可能會發現它在實踐中比您在這裏的速度更快。

Answer 2

我不知道任何算法會比線性時間運行的解決方案漸近地快。但是，您可以執行以下操作來減少常量：

1. 使用bfs而不是dfs：您爲每個函數調用支付開銷！
2. 使用int[][]而非Map<Integer, ListArray<Integer>>（可能Map<Integer, int[]>就足夠了）：首先的int[]訪問速度更快的ListArray的訪問，其次，你不必做的int拳擊/拆箱到Integer。