Articulation Point (단절점)을 이용하여 Biconnected Component (이중 연결 요소) 을 어떻게 찾을 수 있을까?
먼저, Biconnected Component의 정의를 살펴보자
Definition of Biconnected Component G' of G : Graph G의 maximal Biconnected Subgraph
1) Maximal 해야하고
2) Biconnected여야 한다.
Key Property : G의 Biconnected Component 는 G의 Edge들을 Partitioning할 수 있으며 각각의 Biconnected는 오직 한 의 Articulation Point 만을 공유한다.
proof
Contradiction.
만약 Graph G의 서로 다른 Biconnected Component B1, B2가 존재하고 B1 B2가 서로 다른 두 개의 Articulation Point A1, A2를 공유한다고 하자.
그러면 B1 U B2 에서 A1 을 제거했을 때 A1을 제거한 B1 - A1 은 connected 이고 B2 - A1도 connected 이다. 그리고 B1 - A1 과 B2 - A1은 A2를 공유하고 있으므로 (B1 - A1) U (B2 - A1) 은 connected이다.
따라서 B1과 B2는 maximality를 잃게되므로 두 개의 Articulation Point를 공유하는 서로 다른 Biconnected Component는 존재할 수 없다.
Key Property로부터 이런 발상을 떠올릴 수 있다.
"Articulation Point를 분기점으로, Biconnected Component를 찾을 수 있지 않을까?"
이전 포스팅("How to Find Articulation Point with DFS" : https://velog.io/@rkddlfah02/How-To-Find-Articulation-Point-with-DFS)에서 다룬 Articulation Point를 판별하는 로직에서 Articulation Point를 발견하면 그 전까지 탐색한 vertex와 vertex와 incident한 edge들이 Biconnected Component를 구성할 것이다.
이 Idea로 의사코드를 구현하면 다음과 같다.
Pseudo Code
global variable Counter = 1
#pre[v] : v를 첫 방문한 순서
#low[v] : v의 descendant u(u=v일 수 있음)와 incident한 Back-Edge (u,w)가 존재할 경우 low[v] = min(pre[u], pre[w])로 정의
func DFS(v):
visited[v] = True
pre[v] = low[v] = Counter++
for u adjacent to v
if visited[u] = True
stack.push( (v,u) )
low[v] = min(low[v], pre[u])
else
stack.push((v,u))
DFS(u)
low[v] = min(low[v] , low[u])
if low[u] >= pre[v]
pop all edges in stack while (u,v) appears.
and the edges compose Biconnected Component