4. Biconnected Component

송민영·2026년 9월 21일
알고리즘

알고리즘

목록 보기
4/5

목차

  1. 개념
  2. DFN
  3. Articulation Point
  4. Biconnected Componenet
  5. Back Edge
  6. Low
  7. Articulation Point 판별
  8. Stack 이용
  9. BCC 출력

1. 개념

  • 그래프를 단절점(Articulation Point) 기준으로 나누는 방법
  • 아이디어: Biconnected Component(BCC)는 vertex가 아닌 edge를 기준으로 생각 (목차 3&4 참조)
    - 한 vertex에는 여러 개의 BCC에 포함 가능
    - 하나의 edge는 오로지 하나의 BCC에만 포함 가능
  • Biconnected Component(BCC)를 구하기 위해서는 간략하게 다음과 같은 알고리즘을 생각할 수 있다
	1) DFN: DFS를 통해 각 vertex의 방문 숫자(DFN, DFS Number)를 기록한다
    2) Low: Back Edge를 이용하여 도달할 수 있는 가장 빠른 vertex의 DFN을 찾는다
    3) Articulation Point(child) 판별법: low[v]>=dfn[u] (u: parent / v: child) 를 만족하는 u가 Articulation Point(단절점)이다.
    4) Articulation Point(root) 판별법: (DFS tree에서) root의 자식이 2개 이상이면 root는 Articulation Point이다.
    5) Stack: dfs를 통해 어떤 BCC인지 확정되지 않은 edge를 저장하는 공간
    6) BCC 구성하기: Articulation Point가 확정되면, edge를 stack에서 꺼내와 BCC 구성하기

2. DFN (DFS Number)

  • 단절점을 찾기 위해 DFS를 진행하며 각 vertex가 몇 번째로 방문되었는지 기록하는 array
  • 정의 dfn[v] = (dfs에서) vertex인 'v'가 몇 번째로 방문했는지 기록
<java>

List<Integer>[] adjList;	//graph
boolean[] visited;	//방문 여부 확인

int sequence = 1; 	//방문한 순서 count
int[] dfn;			//dfn (dfs number)
...

// BCC - DFN 함수 구현
// v: 현재 vertex 
// u: parent
void bc(int v, int u){
	visited[v] = true;			//방문 여부 기록
	dfn[v] = sequence++;		//방문 순서 기록
    
    // v의 인접 vertex 'e'에 대한 dfs 실행
    // 주의! v의 child가 아닌 단순한 '인접 vertex'임
    for(int e: adjList[v]){
    	if(!visited[e]) {
        	bc(e, v);
      		...
        }
    }
    
    ...
}

예시)

3. Articulation Point & 4. Biconnected Component

  • Articulation Point(단절점) 특정 vertex를 제거했을 때, 두 개 이상의 component로 나눌 수 있는 vertex
  • Biconnected Component 임의의 두 정점 사이에 두 개 이상의 vertex-disjoint path가 존재하는 최대 부분그래프
  • BCC는 단절점을 기준으로 나뉜다.

예시)

  • 원본
  • 분절점 C
  • 분절점 G
  • BCC

5. Back Edge

  • 현재 vertex에서 DFS tree상 자신의 ancestor(조상) 정점으로 연결되는 edge
  • 주의! DFS tree상 본인의 parent는 미포함 (더 위인 ancestor이어야 함)
  • Back Edge 조건 (현재 vertex 'v' - 인접 vertex 'e')
    • 이미 방문 완료 (visited[e] = true)
    • parent는 미포함 (e!=parent)
    • 현재 'v'보다 먼저 방문했었어야 함 = 더 위쪽에 있는 간선 찾기 (dfn[e] < dfn[v])
<java>

List<Integer>[] adjList;	//graph
boolean[] visited;	//방문 여부 확인

int sequence = 1; 	//방문한 순서 count
int[] dfn;			//dfn (dfs number)
...

// BCC - DFN 함수 구현
// v: 현재 vertex 
// u: parent
void bc(int v, int u){
	visited[v] = true;			//방문 여부 기록
	dfn[v] = sequence++;		//방문 순서 기록
    
    // v의 child인 'e'에 대한 dfs 실행
    for(int e: adjList[v]) {
    	if(!visited[e]) {
        	bc(e, v);
      		
        // 현재 'v'에 대한 back edge 찾기    
        } else if(e!=u && dfn[e]<dfn[v]) {
      		
        
        }
    }
    
    ...
}

6. Low

  • 분절점을 찾기 위한 도구

  • 정의 low[v] = subtree of 'v'가 Back Edge를 통해 얼마나 위쪽 ancestor(조상)까지 올라갈 수 있는지를 나타내는 값

  • low[v]가 갱신될 수 있는 두 가지 케이스

    • Back Edge의 발견

      • Back Edge가 발견 -> v가 ancestor(조상)으로 가는 edge가 존재
      • ancestor(조상)으로 갈 수 있으므로 low[v]가 dfn[e]로 더 작아질 가능성 존재
      • low[v] = Math.min(low[v], dfn[e])
      ex) 1->2->3->4->5->6->7 (->2)
  1) vertex '7'에서 vertex '2'로 갈 수 있는 edge 존재
  2) low[7] = Math.min(low[7], dfn[2]) = Math(7, 2) = 2로 갱신

    • 해당 'v'의 subtree에 대한 모든 DFS가 끝남

      • 해당 'v'의 subtree에 해당하는 vertex의 low가 끝남

      • 재귀적으로 return하며 low[v] 자동적으로 초기화

      • low[v] = Math.min(low[v], low[e])

        ex) 1->2->3->4->5->6->7 (->2)
     1) low[7]=2로 갱신 후, vertex '7'에 대한 child가 없으니 return
     2) vertex '6'에 대한 low[6] = Math.min(low[6], low[7]) = Math.min(6, 2) = 2로 갱신
     3) vertex '5'에 대한 low[5] = Math.min(low[5], low[7]) = Math.min(5, 2) = 2로 갱신
     4) ... 위 알고리즘을 통해 low[3]까지 2로 갱신
      
<java>

List<Integer>[] adjList;	//graph
boolean[] visited;	//방문 여부 확인

int sequence = 1; 	//방문한 순서 count
int[] dfn;			//dfn (dfs number)
int[] low;			//low

// BCC - DFN 함수 구현
// v: 현재 vertex 
// u: parent
void bc(int v, int u){
	visited[v] = true;			//방문 여부 기록
	dfn[v] = sequence++;		//방문 순서 기록
    
    // v의 child인 'e'에 대한 dfs 실행
    for(int e: adjList[v]) {
    	if(!visited[e]) {
        	bc(e, v);
            //*2)번 조건으로 해당 'v'의 subtree에 대한 low[v] 갱신
      		low[v] = Math.min(low[v], low[e]);
            
        // 현재 'v'에 대한 back edge 찾기    
        } else if(e!=u && dfn[e]<dfn[v]) {
   
            //*1)번 조건으로 Back Edge 발견 후 low[v] 갱신
            low[v] = Math.min(low[v], dfs[e]);
        
        }
    }
    
    ...
}

7. Articulation Point 판별

  • 모든 low가 갱신되었음을 전제로 함
  • 일반적인 vertex low[e]>=dfn[v]
    - low[e]<dfn[v] : v보다 더 위쪽으로 갈 수 있는 back edge 존재
    • 따라서, 인접 vertex 'e'에서 더 위쪽으로 못가는 지점이 단절점
  • DFS root root의 child vertex >= 2
    - DFS tree에서 root가 2개 이상의 child를 가지면 항상 root는 Articulation Point
<java>

List<Integer>[] adjList;	//graph
boolean[] visited;	//방문 여부 확인

int sequence = 1; 	//방문한 순서 count
int[] dfn;			//dfn (dfs number)
int[] low;			//low

// BCC - DFN 함수 구현
// v: 현재 vertex 
// u: parent
void bc(int v, int u){
	visited[v] = true;			//방문 여부 기록
	dfn[v] = sequence++;		//방문 순서 기록
    
    // v의 child인 'e'에 대한 dfs 실행
    for(int e: adjList[v]) {
    	if(!visited[e]) {
        	bc(e, v);
            //*2)번 조건으로 해당 'v'의 subtree에 대한 low[v] 갱신
      		low[v] = Math.min(low[v], low[e]);
            
            //*모든 low가 갱신됨 -> 단절점 찾기
            if (low[e] >= dfn[v]) {}

            
        //현재 'v'에 대한 back edge 찾기    
        } else if(e!=u && dfn[e]<dfn[v]) {
   
            //*1)번 조건으로 Back Edge 발견 후 low[v] 갱신
            low[v] = Math.min(low[v], dfn[e]);
        
        }
    }
    
    ...
}

8. Stack 이용

  • stack 추가 조건
    • 아직 방문하지 않은 vertex로 가는 edge
    • 조상으로 가는 방문이력이 있는 edge
<java>

List<Integer>[] adjList;	//graph
boolean[] visited;	//방문 여부 확인

int sequence = 1; 	//방문한 순서 count
int[] dfn;			//dfn (dfs number)
int[] low;			//low
Stack<Edge> stack;	//edge를 임시저장하는 stack

// BCC - DFN 함수 구현
// v: 현재 vertex 
// u: parent
void bc(int v, int u){
	visited[v] = true;			//방문 여부 기록
	dfn[v] = sequence++;		//방문 순서 기록
    low[v] = dfn[v];			//low 초기화 (초기에는 dfn과 같음)
    
    // v의 child인 'e'에 대한 dfs 실행
    for(int e: adjList[v]) {
    	if(!visited[e]) {
        	// 방문하지 않은 edge 발견 -> stack에 추가 (Tree Edge)
            stack.push(new Edge(v, e));
        
        	bc(e, v);
            //*2)번 조건으로 해당 'v'의 subtree에 대한 low[v] 갱신
      		low[v] = Math.min(low[v], low[e]);
            
            // 모든 low가 갱신됨 -> 단절점 찾기
            if (low[e] >= dfn[v]) {
				//TODO: BCC 구성하기
            }

            
        // 현재 'v'에 대한 back edge 찾기    
        } else if(e!=u && dfn[e]<dfn[v]) {
        	// back edge 발견 -> stack에 추가 (Back Edge)
   			stack.push(new Edge(v, e));
            
            //*1)번 조건으로 Back Edge 발견 후 low[v] 갱신
            low[v] = Math.min(low[v], dfn[e]);
        
        }
    }
}

9. BCC 구성하기

  • BCC 구성하기 Articulation Point를 기점으로 하나의 BCC 구성하기
  • FILO 구조인 Stack이므로, 가장 먼저 들어간 (v, e)까지 꺼내면 종료 (vertex1==v && vertex2==e)
<java>

List<Integer>[] adjList;	//graph
boolean[] visited;	//방문 여부 확인

int sequence = 1; 	//방문한 순서 count
int[] dfn;			//dfn (dfs number)
int[] low;			//low
Stack<Edge> stack;	//edge를 임시저장하는 stack

// BCC - DFN 함수 구현
// v: 현재 vertex 
// u: parent
void bc(int v, int u){
	visited[v] = true;			//방문 여부 기록
	dfn[v] = sequence++;		//방문 순서 기록
    low[v] = dfn[v];			//low 초기화 (초기에는 dfn과 같음)
    
    // v의 child인 'e'에 대한 dfs 실행
    for(int e: adjList[v]) {
    	if(!visited[e]) {
        	// 방문하지 않은 edge 발견 -> stack에 추가 (Tree Edge)
            stack.push(new Edge(v, e));
        
        	bc(e, v);
            //*2)번 조건으로 해당 'v'의 subtree에 대한 low[v] 갱신
      		low[v] = Math.min(low[v], low[e]);
            
            // 모든 low가 갱신됨 -> 단절점 찾기
            if (low[e] >= dfn[v]) {
                //BCC 구성하기
                while(true){
                	Edge edge = stack.pop();
                    //마지막 Tree Edge (v, e)까지 꺼내면 종료
                    if(edge.adjvertex1 == v && edge.adjvertex2 == e){ break; }
                }
            }

            
        // 현재 'v'에 대한 back edge 찾기    
        } else if(e!=u && dfn[e]<dfn[v]) {
        	// back edge 발견 -> stack에 추가 (Back Edge)
   			stack.push(new Edge(v, e));
            
            //*1)번 조건으로 Back Edge 발견 후 low[v] 갱신
            low[v] = Math.min(low[v], dfn[e]);
        
        }
    }
}
profile
송민영
CNU 23th Computer_Engineering
이전 포스트

3. Topological Sort

다음 포스트

5. Kruskal Algorithm

0개의 댓글