Biconnected component(BCC)
maximal biconnected subgraph: 어떠한 graph에서 biconnected subgraph를 골라내는데 그 subgraph가 더이상 늘릴 수 없을때(maximal) 그것을 BCC라고 한다. BCC는 오로지 무방향 그래프에서만 정의되며 BCC의 중요한 특징은 다음과 같다.
1. articulation point 가 없는 subgraph: BCC에서 임의의 노드를 지웠을때 임의의 노드 A,B는 항상 연결되있다.
2. 임의의 a, b node에 대해서 a와 b를 포함하는 cycle이 존재한다.
BCC tarjan Algorithm
BCC를 구하기 위해 Cycle을 확인해야 하고 그 Cycle에 있는 노드들을하나의BCC로 묶으면 된다. 그렇다면 Cycle 확인을 어떻게 할까 BCC는 undirected graph에서만 정의되므로 undirected graph에서 그래프를 탐색한다고 해보자. undirected graph에서 dfs를 수행하면 tree가 만들어지는데 그 트리는 방향성이 있는 트리가 된다. dfs로 그래프를 탐색을 할 때 존재 할 수 있는 edge는 (back edge, forward edge, cross edge, Tree edge)밖에 없다. 그런데 Undirected graph에서는 back edge, Tree edge밖에 존재하지 않는다. 이를 통해 cycle을 구할 수 있는데 그 방법은 아래와 같다.
먼저 구해야하는 정보는 2가지이다.
1. dfn[ i ] : dfs를 할 때 i노드를 몇번째로 방문하는가
2. low[ i ] : 만들어진 dfs tree의 i 노드에서 시작해 어떻게든 edge를 통해 갈 수 있는 가장 작은 dfn
그리고 "DFS를 수행하면서 각각의 노드가 단절점이라면 그 위와 아래의 COMPONENT가 단절되야 한다. " 라는 아이디어를 통해 한 노드(x)에서 DFS TREE의 위치상으로 자손중 low가 dfn[x]보다 작은 것이 있다면 그 노드 x는 단절점이 아니라는것을 구한후 각각의 component를 따로 구한다.
관련 알고리즘 시간복잡도: O(V + E)
덧글|덧글 쓰기|신고