연결 성분을 이해할 수 있다.

Goal

  • 연결 성분(Connected Component)이란
  • 연결 성분(Connected Component)을 찾는 방법

연결 성분(Connected Component)이란

나누어진 각각의 그래프

연결 성분의 특징

연결 성분을 찾는 방법

연결 성분을 찾는 방법은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이용하면 된다.

  1. BFS, DFS를 시작하면 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결 성분이 된다.
  2. 다음에 방문하지 않은 정점을 선택해서 다시 탐색을 시작하면 그 정점을 포함하는 연결 성분이 구해진다.
  3. 이 과정을 그래프 상의 모든 정점이 방문될 때까지 반복하면 그래프에 존재하는 모든 연결 성분들을 찾을 수 있다.

연결 성분의 개수 구하는 방법

boolean[] visited = new boolean[N + 1]; // N: 정ㅇ점의 수
int cntComponent = 0;
// 각 정점에 대해서 한번씩 확인.
for (int i = 1; i <= N; i++) {
    if (!visited[i]) { // 방문했던 정점은 지나치므로, 연결이 떨어진 정점에 대해서만 카운트++
        dfs(arrayLists, i, visited); // dfs 탐색
        cntComponent++;
    }
}

관련된 Post