연결 요소(Connected Component)

게시 2020/03/30 수정 2026/10/07 작성자 August

조회 9 분 읽는 시간

2026-10-07 docs(posts): separate the sections of every post with a thematic break +6 −0
2026-10-06 docs(posts): fill out more thin notes, book chapters and solutions +42 −2
2020-03-30 처음 게시

그래프 중에서는 위 그림과 같이 여러 개로 나누어져 있을 수도 있다. 위 그림을 보고 두 개의 그래프라고 볼 수도 있지만, 하나의 그래프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 그 이유는 정점 사이에 겹치는 것이 없기 때문이다. 연결 요소로 본다면, 나누어진 각각의 그래프를 연결 요소라고 한다. 이때 연결 요소가 될 조건은 다음과 같다.

연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안 된다.

그러므로, 위 그림은 2개의 연결 요소로 이루어져 있다고 볼 수 있다. 연결 요소를 구하는 것은 DFS나 BFS 탐색을 이용해서 할 수 있다.

연결 요소를 조금 더 정확히 보기

두 조건을 합치면 연결 요소는 “서로 경로로 이어진 정점들을 최대한 넓게 묶은 덩어리”다. 첫 번째 조건만 있으면 덩어리의 일부만 떼어 내도 조건을 만족하므로, 두 번째 조건이 “더 넓힐 수 없을 때까지” 묶으라는 뜻을 더한다. 그래서 모든 정점은 정확히 하나의 연결 요소에 속하고, 간선이 하나도 없는 정점은 그 자체로 연결 요소 하나가 된다.

여기서 말하는 연결 요소는 방향 없는 그래프(무방향 그래프) 기준이다. 방향 그래프에서는 A에서 B로 갈 수 있어도 B에서 A로 못 갈 수 있으므로 “연결되어 있다”의 뜻이 달라지고, 서로 오갈 수 있는 정점끼리 묶는 강한 연결 요소(strongly connected component)라는 별도의 개념을 쓴다.

왜 DFS나 BFS로 구할 수 있는가

DFS나 BFS는 시작 정점에서 경로로 닿을 수 있는 모든 정점을 방문하고, 닿을 수 없는 정점은 방문하지 않는다. 이것이 정확히 시작 정점이 속한 연결 요소다. 따라서 다음 과정을 반복하면 된다.

아직 방문하지 않은 정점을 하나 고른다.
그 정점에서 DFS(또는 BFS)를 돌려 닿는 정점을 모두 방문 처리한다. 이 정점들이 연결 요소 하나다.
연결 요소 개수를 1 늘리고, 방문하지 않은 정점이 남아 있으면 1로 돌아간다.

탐색을 시작한 횟수가 곧 연결 요소의 개수다. 한 번 방문 처리된 정점은 다시 탐색의 시작점이 되지 않으므로, 같은 연결 요소를 두 번 세는 일이 없다.

<hr />

연결 요소 관련 문제

BOJ 11724. 연결 요소의 개수

문제링크 : https://www.acmicpc.net/problem/11724

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

정점은 최대 1,000개이고 간선은 같은 간선이 한 번씩만 주어진다. 정점 번호는 1부터 N까지다.

  
#include <cstdio>
#include <vector>
using namespace std;
vector<int> a[1001];
bool check[1001];

void dfs(int node) {
    check[node] = true;
    for (int i=0; i<a[node].size(); i++) {
        int next = a[node][i];
        if (check[next] == false) {
            dfs(next);
        }
    }
}
int main() {
    int n, m;
    scanf("%d %d",&n,&m);
    for (int i=0; i<m; i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    int components = 0;
    for (int i=1; i<=n; i++) {		// 모든 인접 리스트를 순회하면서
        if (check[i] == false) {	// 방문하지 않은 노드가 있다면
            dfs(i);			// 하나의 연결 요소 모두 방문
            components += 1;		// 연결 요소의 수 증가
        }
    }
    printf("%d\n",components);
    return 0;
}

코드 읽기

vector<int> a[1001]은 인접 리스트다. 정점 번호가 1부터 시작하므로 크기를 N+1인 1001로 잡았다. 그래프 글에서 정리했듯이 인접 리스트는 실제 간선 수만큼만 공간을 쓴다.
입력에서 a[u].push_back(v)와 a[v].push_back(u)를 둘 다 하는 이유는 방향 없는 그래프이기 때문이다. 한쪽만 넣으면 v에서 u로 가는 길이 없는 것처럼 탐색된다.
dfs(node)는 정점을 방문 처리한 뒤, 인접한 정점 중 방문하지 않은 곳으로 재귀 호출한다. 호출이 끝나면 node가 속한 연결 요소의 모든 정점이 check에 표시되어 있다.
main의 마지막 반복문이 위의 1~3단계다. 1번부터 N번까지 차례로 보면서 아직 방문하지 않은 정점을 만날 때마다 DFS를 한 번 돌리고 개수를 1 늘린다.

예를 들어 정점이 6개이고 간선이 1-2, 2-5, 5-1, 3-4, 4-6이라면, i=1에서 DFS가 1, 2, 5를 방문하고 개수가 1이 된다. i=2는 이미 방문했으므로 건너뛴다. i=3에서 DFS가 3, 4, 6을 방문하고 개수가 2가 된다. 나머지는 모두 방문되어 있으므로 답은 2다.

시간 복잡도

모든 정점은 정확히 한 번 방문 처리되고, 각 정점에서 인접 리스트를 한 번씩 훑는다. 방향 없는 그래프에서는 간선 하나가 양쪽 인접 리스트에 한 번씩 들어가므로 인접 리스트 전체 길이는 2M이다. 따라서 전체 시간은 O(N + M)이다. 인접 행렬로 저장했다면 정점마다 N칸을 모두 확인해야 하므로 O(N²)이 된다.

재귀 깊이

재귀 DFS의 호출 깊이는 최악의 경우 정점 수만큼 깊어진다. 정점이 일렬로 이어진 그래프라면 1,000단계까지 들어간다. 이 문제의 제한에서는 문제가 없지만, 정점이 수십만 개인 문제에서는 스택 오버플로가 날 수 있다. 그럴 때는 BFS를 쓰거나, 명시적인 스택으로 DFS를 반복문으로 바꾸면 된다. 연결 요소의 개수만 필요하다면 어떤 순서로 방문하든 결과는 같다.

<hr />

참고한 자료외부 출처 1 · 블로그 글 1

외부 출처

BOJ 11724. 연결 요소의 개수Baekjoon Online Judge

이 블로그의 관련 글

BOJ 2667. 단지번호붙이기2020-03-30같은 원리로 격자 위의 덩어리를 세는 문제로 · 가 있다.

Notes, Programming