갈 수 있는 정점을 모두 모은다
한 정점에서 출발해 간선을 따라 도달할 수 있는 정점을 전부 모으면 그 정점이 속한 연결 성분의 정점 집합을 얻는다. 일부만 고르고 멈추면 더 큰 연결 부분이 남을 수 있다.
작은 예
A—B—C로 이어진 부분과 D—E로 이어진 부분이 서로 떨어져 있다면 연결 성분은 두 개다. 여기에 어떤 간선도 없는 F를 추가하면 F 하나가 세 번째 성분이 된다.
겹치지 않는 이유
두 연결 성분이 정점 하나를 공유하면 그 정점을 거쳐 양쪽의 정점들이 서로 이어진다. 따라서 서로 다른 두 성분으로 남을 수 없다. 연결 성분의 정점 집합들은 전체 정점 집합을 분할한다.
유향 그래프에서는
방향을 따라 서로 도달할 수 있는 정점들을 묶는 강연결 성분과, 방향을 무시했을 때의 연결 성분은 다르다. 유향 그래프를 다룰 때는 어떤 연결 개념을 사용하는지 명시한다.
관련 문서
연결 그래프 / 무향 그래프 / 유향 그래프 / 집합의 분할 / 정점 (그래프 이론) / 간선 (그래프 이론) / 동치 관계