그래프 Connected Components: DFS, BFS와 Union-Find

Connected Component는 무방향 그래프에서 서로 경로로 연결된 정점들의 최대 집합입니다.

전체 그래프가 하나의 Component라면 Connected Graph이고, 여러 개라면 Disconnected Graph입니다.

핵심 아이디어

방문하지 않은 정점마다:

1. DFS 또는 BFS를 시작합니다.
2. 해당 탐색에서 도달한 모든 정점은 하나의 Component입니다.
3. 다음 미방문 정점에서 반복합니다.

JavaScript

function components(graph) {
  const visited = new Set();
  const result = [];

  for (const start of Object.keys(graph)) {
    if (visited.has(start)) continue;

    const stack = [start];
    const component = [];

    visited.add(start);

    while (stack.length) {
      const node = stack.pop();
      component.push(node);

      for (const next of graph[node] ?? []) {
        if (!visited.has(next)) {
          visited.add(next);
          stack.push(next);
        }
      }
    }

    result.push(component);
  }

  return result;
}

SCC와의 차이

Connected Components는 주로 Undirected Graph에 사용됩니다.

Directed Graph에서는 Weakly Connected Components와 Strongly Connected Components를 구분합니다.

Union-Find

Edge가 동적으로 추가되는 경우 DSU를 사용하면 Component 병합과 Connectivity Query를 매우 효율적으로 처리할 수 있습니다.

활용

• 소셜 네트워크의 독립 그룹
• Number of Islands
• Network Partition
• 이미지 Connected Regions
• 장치 그룹 분석

복잡도

Adjacency List 기준:

O(V + E)

정리

방문하지 않은 정점에서 시작하는 각 DFS/BFS는 하나의 Connected Component를 찾습니다.