Connectedcomponent
-
Graph - Connectedcomponent( 연결 성분 )C 자료구조/Graph 2020. 7. 11. 23:14
내용 앞에서 만든 DFS 내용을 그대로 가지고 와서 만든다. 1. 개념 연결 성분이란 최대로 연결된 부분 그래프를 말한다. 즉, 연결된 부분 그래프들 중에서 크기가 최대인 것을 연결 성분이라고 한다. 아래의 그래프에는 2개의 연결 성분이 있다. 위의 그래프를 연결 성분 함수를 호출하면 연결성분을 표시한 배열Visit는 아래의 그림과 같다. 즉, 정점의 집합 { A, B, C }와 집합 { D, E }가 연결 성분임을 알 수 있다. 연결 성분을 찾기 위해서 깊이 우선 탐색이나 너비 우선 탐색을 이용한다. 먼저, 그래프 상의 임의의 정점을 선택해 깊이 우선 탐색이나 너비 우선 탐색을 시작하면 시작 정점과 연결되어 있는 모든 정점들이 출력된다. 다음에 방문 안된 정점을 선택해서 다시 탐색을 실행하면 그 정점을..