Graph - Connectedcomponent( 연결 성분 )

<C언어로 쉽게 풀어쓴 자료구조 > 내용

 

앞에서 만든 DFS 내용을 그대로 가지고 와서 만든다.

 

1. 개념

연결 성분이란 최대로 연결된 부분 그래프를 말한다.

즉, 연결된 부분 그래프들 중에서 크기가 최대인 것을 연결 성분이라고 한다.

 

아래의 그래프에는 2개의 연결 성분이 있다.

위의 그래프를 연결 성분 함수를 호출하면

연결성분을 표시한 배열Visit는 아래의 그림과 같다.

즉, 정점의 집합 { A, B, C }와 집합 { D, E }가 연결 성분임을 알 수 있다.

연결 성분을 찾기 위해서 깊이 우선 탐색이나 너비 우선 탐색을 이용한다.

먼저, 그래프 상의 임의의 정점을 선택해 깊이 우선 탐색이나 너비 우선 탐색을 시작하면

시작 정점과 연결되어 있는 모든 정점들이 출력된다.

다음에 방문 안된 정점을 선택해서 다시 탐색을 실행하면 그 정점을 포함하는 연결 성분이 찾아진다.

이러한 방법으로 그래프 상의 모든 정점이 방문될 때까지 이 과정을 되풀이하면 그래프에 존재하는 모든 연결 성분들을 찾을 수 있다.

 

깊이 우선 탐색 알고리즘을 이용해 연결 성분을 찾고자 할 경우,

앞에서 작성한 깊이 우선 탐색의 프로그램 코드에서 정점 방문을 표시하는 문장인

pGraph->pVisit[StartVertex] = 1 을 pGraph->pVisit[StartVertex] = pGraph->count로 바꾸고,

FindConnectedComponent함수에서 pGraph->count를 증가시키면서

반복적으로 깊이 우선 탐색 프로그램을 호출한다.

count 변수는 Graph구조체에 선언한다.

 

해당 작업이 끝나면, 배열 pGraph->pVisit에는 같은 번호로 표시된 정점들은 하나의 연결 성분을 구성하게 된다.

 

2. 프로그램 구현

< Graph.h >

< Graph.c >

 

< main.c >

프로그램 실행 결과

3. 헤더 파일 & 소스 파일

common.h

0.00MB

Graph.c

0.00MB

Graph.h

0.00MB

main.c

0.00MB