java - 优化此代码以查找连接的组件？

Question

我有无向图，我需要找到图中连通分量的数量。我将图形表示为 Map<Integer, ArrayList<Integer>> map (节点:连接节点的列表)。然后我浏览该 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 慢，但常数因子非常低，您可能会发现它在实践中比这里的更快。