[알고리즘] Biconnect Component : 이중 연결 성분

 

이중 연결 성분(Biconnect Component)란?

 

이중 연결 성분이란, 무방향 그래프의 연결 성분에서 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분을 뜻한다.

 

이때, 연결 성분이란 그래프에서 서로 연결되어 있는 정점들을 말한다. 예를 들어, [1, 2, 3, 4, 5], [6, 7], [8, 9, 10]는 3개의 연결 성분으로 구성되었다고 볼 수 있다. 또한 단순 경로란, 경로 상의 정점이 모두 다른 경로를 말한다.

 

즉, 이중 연결 성분이란, 무방향 그래프의 연결되어 있는 정점 리스트인데, 이 리스트의 임의의 두 점 간의 경로 상에 있어서 정점이 중복되지 않는 경로가 두 개이상 존재하다는 것을 의미한다.

 

 

아래 예시와 함께 그 의미를 한 번 더 살펴보자.

 

 

 

위 그래프는 지금까지 살펴본 이중 연결 성분의 개념에 의하면, 3개의 이중 연결 성분이 존재한다.

[0, 1, 2, 3], [3, 5], [4, 5, 6]이다.

이유가 헷갈린다면, 각 이중 연결 성분에서 임의의 두 점 사이에 단순 경로가 두 개 이상임을 직접 확인하자. 참고로 2개의 정점으로 구성된 3, 5도 단순 경로가 두개라고 취급한다.

 

여기서 우리는 새로운 용어를 정의할 수 있다.

우선, 단절 정점(Cut point, Articulation Point)이다. 이 그래프에서 연결 성분의 정점 중, 하나의 정점을 삭제했을 때 두 개 이상의 연결 성분으로 분리될 때의 정점을 의미한다.

 

위 그래프에서 3과 5가 각각 단절 정점이다. 좌측의 [0, 1, 2] 우측의 [4, 5, 6]과 같이 두 개의 연결 성분으로 나뉘는 것을 직접 확인해 보면 이를 알 수 있다.

 

다음으로 다리 간선(Bridge)이다. 이는 간선을 제거했을 때, 두 개 이상의 연결 성분으로 분리될 때 삭제된 간선을 말한다.

이제, 이중 연결 성분이 어떤 것인지 살펴보았으니, 어떤 방법으로 구현할 수 있는 지 확인해보자.

 

 

 

 

 

 

이중 연결 성분(Biconnect Component)구현을 위한 DFS

 

 

결론부터 말하자면, 이중 연결 성분은 단절 정점의 확인과 특정 정점을 통해 이어진 모든 정점을 탐색하고 돌아왔을 때, 이를통해 찾고 출력 가능하다.

그 과정을 이해하기 위해 아래 그림을 참고해보자.

 

 

 

 

 

여기서 간선들은 서로 이어져 있는데, 이때 사이클을 생성하는 간선이 존재한다.

이를 뒷간선이라고 하는데, 뒷간선 (2, 0)은 사이클 [0, 3, 2, 0]을 생성하고, 뒷간선(1, 0)은 사이클 [0, 3, 2, 1, 0]을 생성한다. 또한 뒷간선 (6, 5)는 사이클 [5, 4, 6, 5]를 생성한다.

 

이처럼 뒷간선을 통해 만들어진 사이클 상의 정점들은 하나의 이중 연결 성분에 속한다는 것을 기억하자.

 

이러한 사이클의 역할은 사이클 안의 요소들을 같은 그룹으로 묶어주는 역할을 한다. 사이클이 왼쪽 그림처럼 사이클이 겹쳐지더라도, 결국에 하나의 이중 연결 요소이므로, 같은 그룹에 속할 수 있도록 만들어진다.

 

 

 

 

 

 

 

 

사이클을 형성하는 것 이외의 실질적으로 이중 연결 성분을 찾는 조건은 바로 단절 정점 찾기이다.

앞서 말했듯이 단절 정점은 두 개 이상의 이중 연결 성분으로 나누어주는 정점을 말한다. 이는 곧 단절정점을 찾는다면, 이중 연결 성분의 구분이 가능하다는 것이다.

아래 예시는 위 신장 트리를 그래프로 나타낸 것이다. 

 

 

 

 

 

결국 DFS를 수행하며, 사용하는 간선을 스택 자료 구조에 저장하고, 뒷간선을 통해서 사이클을 만든다. 사이클을 안에 있는 모든 정점들은 이중 연결 성분의 요소들이며, 여러 개의 사이클이 생기더라도 같은 이중 연결 성분 내에서는 같은 값만 주면 되기 때문이 큰 상관이 없다.

같은 값에 대해서는 뒤에서 설명하겠다.

 

 

 

 

 

이중 연결 성분(Biconnect Component)구현

 

 

 

이중 연결 성분 알고리즘은 DFS를 수행하며, 방문 번호 (dfsnum) 을 매긴다. 이를 통해 방문 순서를 체크할 수 있는데 앞에서 말한 같은 값을 이 dfsnum에 두는 것이다.

 

결국 가장 작은 dfsnum을 가진 정점에 도달할 수 있냐의 여부를 따지는 셈이 되는데, 이를 표시하기 위해 lownum이라는 배열을 사용해야 한다.

 

다시말해 dfsnum은 방문순서(1, 2, 3, 4, 5...)를 나타낸 것이고, lownum은 단절 정점에 도달하기 까지 같은 dfsnum으로 이중 연결 성분을 구분하기 위해 있는 것이다. (1, 1, 1, 2, 2, 3..)

 

아래는 자바 언어로 구현된 Biconnect Component 예시이다.

 

 

class BiconnectedComponents {
    private int sequence = 1;
    // 방문 순서 배열
    private int[] dfsnum;
    // 이중 연결 성분 구분용
    private int[] lownum;
    private List<List<Integer>> graph;
    private Stack<Edge> edgeStack;
    class Edge {
        int u, v;
        public Edge(int u, int v) {
            this.u = u;
            this.v = v;
        }
    }

	// 초기화
    public BiconnectedComponents(int n) {
        dfsnum = new int[n];
        lownum = new int[n];
        graph = new ArrayList<>();
        edgeStack = new Stack<>();

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    

	// 아예 떨어져 있는 연결 성분을 위해 전부 탐색
    public void find() {
        for (int i = 0; i < dfsnum.length; i++) {
            if (dfsnum[i] == 0) {
                biconnected(i, -1);
            }
        }
    }

    public void biconnected(int v, int u) {
    	// v 방문
        dfsnum[v] = lownum[v] = sequence++;

		// v 인접 요소 w 탐색
        for (int w : graph.get(v)) {
			
            // 간선 추가
            if (w != u && dfsnum[w] < dfsnum[v]) {
                edgeStack.push(new Edge(v, w));
            }
            // 인접 요소 w가 방문되지 않았다면 수행
            if (dfsnum[w] == 0) {
            	// w 방문
                biconnected(w, v);
                // v와 w의 lownum 중 작은 값을 v로.
                lownum[v] = Math.min(lownum[v], lownum[w]);
                // w가 단절 정점인 경우
                if (lownum[w] >= dfsnum[v]) {
                    System.out.println("BiconnectedComponents의 각 간선: ");
                    // 간선 pop
                    while (true) {
                        Edge edge = edgeStack.pop();
                        System.out.println("(" + edge.u + ", " + edge.v + ")");
                        if (edge.u == v && edge.v == w) {
                            break;
                        }
                    }
                }
            // 오해하면 안되는 것이 위 w 방문 조건을 통과했다는 것 자체가 뒷 간선이 생겼다는 말임
            // 만약 뒷 간선이 생긴다면, v의 lownum을 사실 상 뒷 간선이 가리키는 정점의 dfsnum으로 업데이트
            } else if (w != u) {
                lownum[v] = Math.min(lownum[v], dfsnum[w]);
            }
        }
    }


}

 

 

실행 순서에 관해 다시한번 그림과 함께 설명하겠다.

 

bc.addEdge(0, 2);
bc.addEdge(0, 1);
bc.addEdge(0, 3);
bc.addEdge(2, 3);
bc.addEdge(1, 2);
bc.addEdge(3, 5);
bc.addEdge(5, 6);
bc.addEdge(6, 4);
bc.addEdge(4, 5);

 

방문 순서 자체는 이렇게 에지를 무엇을 먼저 넣었냐에 따라 결정된다. 0, 2가 제일 먼저 넣었다고 가정해보자.

 

1. 0부터 시작하여 2부터 갔다고 하자. 이 때 처음 방문하는 정점에 대해서는 항상 edgestack에 추가된다. 이후, dfsnum = 0인 조건에 걸려 재귀적으로 다음 정점에 대한 방문을 수행한다. 

dfsnum[0] = lownum[0] = 1;
dfsnum[1] = lownum[1] = 1;

edge stack : [(0-2)]

2. 2에서 3을 재귀적으로 들어간다. 3에서는 for문으로 두가지 분기가 나뉜다. 중요한 것은 for문 분기가 재귀보다 먼저라는 것이다. 이것을 기억하고 다음 단계로 가보자.

dfsnum[2] = lownum[2] = 2;

edge stack : [(2-3), (0-2)]

3. 3에서는 첫번째 분기로 0으로 들어간다. 이때 0은 이미 방문한 정점이므로, dfsnum[v] == 0 조건에 걸리지 않고 아래의 else if 조건에 걸리게 된다. 이 조건에 의해서, 0의 dfsnum으로 3의 lownum이 지정된다.

dfsnum[3] = lownum[3] = 3;
-> lownum[3] = dfsnum[0]이되므로, 1이된다.

edge stack : [(3-0), (2-3), (0-2)]

4. 재귀함수에 의해 3으로 다시 돌아오고 실행하지 못한 분기인 5로 방문을 수행한다.

dfsnum[5] = lownum[5] = 4;

edge stack : [(3-5) ,(3-0), (2-3), (0-2)]

5. 5에서 6으로 마찬가지로 재귀 방문해주며, 마찬가지로 4로 방문해준다.

dfsnum[6] = lownum[6] = 5;
dfsnum[4] = lownum[4] = 6;

edge stack : [(6, 4), (5, 6), (3-5), (3-0), (2-3), (0-2)]

 

6. 4에서 5를 방문할 때는 이미 방문한 정점이므로, 뒷간선이 생긴다. lownum을 적용시켜주자.

lownum[4] = dfsnum[5];
즉, 4가 저장된다.

edge stack : [(4, 5), (6, 4), (5, 6), (3-5), (3-0), (2-3), (0-2)]

 

7. 재귀 방문을 마치고, 4에서 6으로 돌아오며 6에서 5로 돌아온다. 이때 각 lownum의 값이 세팅된다.

 

lownum[6] = lownum[4]이 된다. 즉, 4가 저장된다.
lownum[5]는 이미 4가 저장되어 있다.

edge stack : [(4, 5), (6, 4), (5, 6), (3-5), (3-0), (2-3), (0-2)]

 

8. lownum[5]와 dfsnum[5]가 같으므로, lownum[w] = dfsnum[v]의 조건이 만족된다. 즉, 출력이 된다. (특정 정점에서 이어진 모든 정점을 탐색 후 돌아옴)

출력 : (4, 5), (6, 4), (5, 6)
스택이 break 될 수 있는 조건은 pop한 edge의 u와 v가 현재 v와 w의 값과 같을 때 수행하고 끝내는 것이다.

edge stack : [(3-5), (3-0), (2-3), (0-2)]

 

9. 다음으로 5에서 다시 3으로 재귀함수가 반환되며, 바로 출력문에 걸리게 된다. 이는 lownum[w] > dfsnum[v]가 항상 만족하기 때문이다. 이는 다리 간선이기 때문에 가능하다. (단절 정점으로 인한 출력)

출력 : (3, 5)

edge stack : [(3-0), (2-3), (0-2)]

10. 이후, 3에서 2로 재귀 함수가 반환되며, lownum이 세팅된다.

lownum[2] = lownum[3], 즉 이전에 설정했던 1 값이 저장된다.

 

edge stack : [(3-0), (2-3), (0-2)]

 

11. 2에서는 분기가 나뉜다. 즉, 1로 가는 부분으로 간다. 이전에 바로 3으로 간 것은 초기에 그래프 생성 시 (2, 3)을 (1, 2)보다 먼저 넣었기 때문이다.

dfsnum[1] = lownum[1] = 7;

edge stack : [(1, 2), (3-0), (2-3), (0-2)]

12. 1에서는 0으로 방문하는데 이미 방문한 노드이므로, lownum을 바꾸어 준다.

lownum[1] = lownum[0]이므로 1이 저장된다.

edge stack : [(1, 0), (1, 2), (3-0), (2-3), (0-2)]

 

13. 재귀 함수가 다시 돌아오며, 2로 돌아온다. 이후, 2에서 0으로 돌아온다. 이후, lownum[w] = dfsnum[v] 조건에 걸려 전부 출력해준다. (특정 정점에서 이어진 모든 정점을 탐색 후 돌아옴)

출력 : (1, 0), (1, 2), (3-0), (2-3), (0-2)

 

 

이중 연결 성분(Biconnect Component)의 수행 시간

 

DFS의 수행 시간이 O(n+m)이며, 스택에 각 간선이 1번 push되고, 1번 pop되는 시간이 O(m)이므로, 총 수행 시간은 O(n+m)이다.