그래프 (7) - 단절점과 단절선

그래프 간선의 분류

단절점/단절선 알고리즘의 원활한 이해를 위해 그래프 간선을 분류하는 방법에 대해 알아보자.

 

유향 그래프에서, dfs를 하여 dfs 스패닝 트리가 형성되면 해당 트리를 기준으로 간선은 4가지로 분류할 수 있다.

tree edge: dfs 트리에 속하는 간선

forward edge: 조상에서 자손으로 향하지만, tree edge는 아닌 간선

backward edge: 자손에서 조상으로 향하는 간선

cross edge: 서로 조상-자손 관계가 아닌 두 정점 간 간선

 

무향 그래프의 경우, 방문하지 않은 정점을 연결하는 간선이 존재한다면 그 간선을 탐색할 것이므로 cross edge는 존재할 수 없다. 또한 방향이 없어 forward edge와 backward edge의 구분이 사라진다. 따라서 tree edge와, tree edge에 속하지 않는 간선들(편의상 backward edge라고 하자)만 남게 된다.

 

 

단절점

단절점(Articulation point)은 무향 그래프에서 해당 정점을 삭제했을 때 그래프가 둘로 쪼개지는, 즉 컴포넌트의 수가 증가하는 정점을 의미한다. 따라서 단절점을 기준으로 그래프를 둘로 나누었을 때, 두 집단 간에는 해당 정점을 통한 경로 외에 다른 우회로가 존재하지 않아야 한다.

 

이 의미를 잘 생각해 보면, 전 편에 다루었던 scc를 구하는 타잔 알고리즘을 응용하여 단절점을 찾아낼 수 있다. 다만 여기서는 무향 그래프에 대해 다루고 있으니, low-link 값을 다시 정의하자.

 

$low[u]$: ($u$나 $u$의 자손 정점에서 (tree edge가 아닌) backward edge를 이용해 도달 가능한 $id$의 최솟값)

 

만약 $u$가 단절점이라면, $u$의 임의의 자손 $v$에 대해 $id[u] \leq low[v]$일 것이다. 다만 tree edge인 경우에는 low값을 업데이트하지 말아야 하므로, 각 노드의 부모를 담는 parent 배열을 만들어서 이를 검사해 준다. 알고리즘은 다음과 같다.

 

1. u에 방문하면, $low[u], id[u]$를 초기화한다.

2. 연결된 정점 $v$를 살펴본다.

2-1. 만약 $v$가 $u$의 부모라면, tree edge이므로 넘어간다.

2-2. $v$에 방문한 적이 있다면, $low[u]=min(low[u], id[v])$로 한다.

2-3. $v$에 방문한 적이 없다면, $parent[v]=u$로 하고 dfs한다. $id[u] \leq low[v]$라면 $u$는 단절점이다. 이후 $low[u] = min(low[u], low[v])$로 갱신한다.

 

def tarjan():
    t = 1
    ids = [0]*(V+1)
    low = [0]*(V+1)
    parent = [0]*(V+1)
    articulation = set()

    def _dfs(u):
        nonlocal t
        low[u] = node_id[u] = t
        t += 1
        for v in adj[u]:
            if parent[u] == v: continue 
            if ids[v]: low[u] = min(low[u], ids[v])
            else:
                parent[v] = u
                _dfs(v)
                if ids[u] <= low[v]: articulation.add(u)
                low[u] = min(low[u], low[v])
    
    for i in range(1, V+1):
        if ids[i] == 0: _dfs(i)
    return articulation

 

 

다만 루트 노드의 경우 1개의 노드와만 연결되어 있어 실제로는 단절점이 아닌 상황에서도 단절점으로 판단하는 문제가 있으므로, 루트의 경우에는 자손들에 대해 2번 이상의 dfs가 필요하다면 단절점으로 파악하는 방식으로 별도로 검사할 수 있다.

def tarjan():
    t = 1
    ids = [0]*(V+1)
    low = [0]*(V+1)
    parent = [0]*(V+1)
    articulation = set()

    def _dfs(u, is_root):
        nonlocal t
        low[u] = node_id[u] = t
        t += 1
        visit = 0
        for v in adj[u]:
            if parent[u] == v: continue 
            if ids[v]: low[u] = min(low[u], ids[v])
            else:
                if is_root: visit += 1
                parent[v] = u
                _dfs(v, False)
                if ids[u] <= low[v] and not is_root: articulation.add(u)
                low[u] = min(low[u], low[v])
        
        if is_root and visit >= 2: articulation.add(u)
    
    for i in range(1, V+1):
        if node_id[i] == 0: _dfs(i, True)
    return articulation

 

 

단절선

단절선(Bridge)은 제거했을 때 컴포넌트의 수를 증가시키는 간선이다. 알고리즘은 단절점을 구할 때와 거의 동일하다. $id[u]<low[v]$라면 간선 $(u, v)$는 단절선으로 볼 수 있다.

def tarjan():
    parent = [0]*(V+1)
    low = [0]*(V+1)
    ids = [0]*(V+1)
    t = 0
    bridges = set()

    def _dfs(u):
        nonlocal t
        low[u] = dfs_id[u] = t
        t += 1
        for v in adj[u]:
            if v == parent[u]: continue
            if ids[v]: low[u] = min(low[u], ids[v])
            else:
                parent[v] = u
                _dfs(v)
                if ids[u] < low[v]:
                    bridges.add(tuple(u, v))
                low[u] = min(low[u], low[v])
    
    for i in range(1, V+1):
        if dfs_id[i] == 0: _dfs(i)
    return bridges

 

 

단절점과 단절선을 구하는 알고리즘은 타잔 알고리즘, dfs의 변형이므로 $O(V+E)$의 시간복잡도를 갖는다.