본문 바로가기

개발새발 개발자/자료 구조

[자료구조] 13-2. 깊이 우선 탐색 알고리즘의 응용 (1)


STL을 이용해 그래프를 구현하는 방법에 대해 복습해보자. 


1. 버텍스와 엣지의 수를 입력받는다.

2. 각각을 엣지 리스트에 넣는다.

3. 정렬한다.


4. 그래프를 만들고 나면 dfs를 구현하기 위해 버텍스의 모든 비지트를 false로 초기화시킨다. 이 함수를 initVisit()라고 한다.

5. 모든 버텍스들에 대해 visit가 false라면(아직 방문하지 않았다면) 그 버텍스에 대해 dfs를 수행하라고 명령한다.


6. 해당 버텍스를 처리할 dfs 함수로 들어온다.

7. 몇 번 버텍스를 방문하고 있는지 출력한다.

8. 버텍스의 visit를 true로 바꿔준다.

9. 해당 버텍스에 연결된 모든 버텍스에 대해서, 아직 방문하지 않은 버텍스가 있다면 dfs를 수행한다.


이처럼 코드는 간단하지만 그만큼 이해가 쉽지 않고 과정에서 굉장히 많은 연산이 구현된다.


사용되는 연산 중 하나는 연결 성분을 찾는 알고리즘이다.


연결 성분이란, 연결된 부분 그래프의 최대치이다. 위와 같은 그래프에서 연결 성분을 찾는다면 1, 2, 3과 또 다른 최대치인 5, 6, 7, 8, 9를 하나씩 연결해서 두 개의 연결 성분이 있다고 말할 수 있다.


연결 성분을 추출하는 알고리즘은 깊이 우선 탐색 알고리즘을 이용해, 한 버텍스에서 방문할 수 있는 모든 버텍스를 방문한다. 최대치를 찾는 것이다.


만약 위의 그래프에 dfs를 수행한다면, 1에서 시작해서 3으로 갔다가 2로 갔다가 더 이상 갈 곳이 없으니 돌아와서 1에서 끝난다. 이렇게 dfs를 수행하는 동안에 방문하는 버텍스들에 대해 같은 인덱스를 부여한다.

 

그 다음으로 아직 방문하지 않은 버텍스가 남아 있으므로 5번에서 dfs를 다시 수행한다.(가장 작은 수이므로) 이번엔 인덱스를 1 증가시켜서 2로 만들고 수행하는 과정에서 모든 버텍스에 인덱스 2를 부여한다. 다시 돌아와서 dfs가 끝나면 인덱스 2번을 갖는 연결 성분이 된다.


코드로 보면 다음과 같다.


1. 연결 성분에 대한 인덱스를 1로 초기화 한다.

2. 모든 버텍스들에 대해 아직 방문하지 않은 버텍스는 dfs를 수행한다. 이때 연결 성분의 인덱스는 idx로 전달한다.

3. i번째 버테스에서 방문할 수 있는 모든 버텍스를 다 방문해 종료가 되면(최대치를 방문하면) idx를 증가시킨다.


그 과정에서 수행되는 dfs는 버텍스와 idx를 함께 전달받는다. 


1. 해당 버텍스의 cc(connected component) 인덱스는 전달받은 idx라고 저장한다.

2. for 루프를 돌리면서 해당 버텍스에 연결된 버텍스들에 대해 idx를 넘겨준다.


이중 연결 성분은 biconnted component, 버텍스들 사이에 두 개 이상의 경로가 존재해서, 연결된 엣지가 제거되어도 연결이 유지되는 연결 성분이다.


0 1 2 3은 버텍스 하나가 제거되어도 연결 상태가 계속 유지되므로 이중 연결 성분이다. 하지만 0 1 2 3 4 5 6의 경우는 그렇지 않다. 2번 버텍스가 제가되면 두 개의 연결 성분으로 분해되기 때문이다.


이중 연결 성분을 찾을 때 중요한 것은 2번 버텍스처럼 어떤 버텍스가 제거되면, 그래프가 두 개로 단절된다는 의미를 지니도록 정의하는 것이다.


그와 같은 버텍스를 분절점이라고 한다. 버텍스 v와 그에 연결된 엣지들을 모두 제거하면 이 그래프가 두 개 이상의 연결 성분으로 분해된다는 의미이다.


예를 들어, 위의 그래프에서 버텍스 2와 6은 분절점이다.


앞의 그래프를 이중 연결 성분으로 분할하면 이렇게 된다. 


이중 연결 그래프는 곧 분절점이 없는, 그래프 자체가 이중 연결 성분인 그래프를 의미한다. 앞의 그래프에서 버텍스 0과 7 사이에 엣지를 그려주면 어떤 버텍스를 제거해도 그래프는 연결 상태가 유지된다.