연결 요소 [ 수정 내역 ] [ 수정 ]

최근 수정: 6년 전

1. 개요

Connected Component.

그래프에서 정점들이 끊어지지 않고 연결되어 있는 덩어리. 쉽게 생각해서 간선을 통해 갈 수 없는 정점이 없다면 한 개의 연결 요소이다.

2. 연결 요소 탐색

DFS나 BFS 탐색으로 구할 수 있다. 한 정점에서 DFS, BFS 등의 탐색을 완료했을 때 아직 방문하지 않은 정점이 있다면 이는 전체 그래프가 하나의 연결 요소가 아니라는 의미이다.

모든 정점에 대해 탐색을 진행하고, 처음 진행할 때 카운트를 1 증가하면 전체 연결 요소의 개수를 구할 수 있다.