Оптимизация этого кода для поиска подключенных компонентов?

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.