절단점 및 다리(구하기)

절단점 및 다리(Articulation Point & Bridge)

  절단점은 그래프G의 정점 중에서 이를 제거했을때(이때 해당 정점에 인접한 간선들도 같이 제거한다) G가 연결되지 않도록 만드는 정점이다. 절단점이 한개도 없는 그래프를 이중 결합 되었다고 한다.

  다리는 그래프 G의 간선 중에서 이를 제거했을때 G가 연결 되지 않게 만드는 간선이다. 이둘을 찾는 문제는 보통 무방향 그래프에 대해서 정의된다.

Algorithms to get Articulation Point and Bridge

  우선 가장 직관적이지만 약간 비효율적인 알고리즘을 소개 하겠다.

첫째. DFS를 수행하여 그래프 G가 몇개의 컴포넌트로 구성되었는지를 파악한다.

둘째. 모든 정점을 한번씩 순회하며 해당정점과 정점에 인접한 간선을 제거한다음              DFS를 수행한다.

셋째. 이때 컴포넌트의 수가 늘어났다면 해당 정점은 절단 점이다.

위 알고리즘은 각 정점마다 DFS를 수행하여야 모든 절단점을 구할수 있기 때문에 O(V^2 + VE)의 시간복잡도를 갖는다. 이 알고리즘 보다 더 효율적으로 절단점과 다리를 찾을 수 있는 알고리즘이 있다.

  이 알고리즘은 절단점 및 다리를 O(V + E)만에 찾아낼 수 있다. 즉 DFS를 한번만 수행하여 모든 절단점과 다리를 찾는것이다. 이를 위해 DFS도중에 두가지 값을 유지 하여야 된다. dfs_num, dfs_low가 이에 해당한다. dfs_num은 정점이 최초로 발견된 순서가 저장된다. dfs_low에는 해당 정점을 루트로 하는 서브 트리에서 도달할 수 있는 최소한의 정점(가장 위쪽 정점)의 번호를 저장한다.  만약 최소한의 번호가 자신의 부모라면 저장 하지 않는다.(이는 역방향 간선이 아닌 양방향 간선이기 때문이다.)

  직관적으로 설명하자면 정점 u가 절단점이 되지 못하는 조건은 다음과 같을 것이다. 정점 u를 루트로 하는 스패닝 서브트리에 속하는 임의의 노드 v가 도달 할 수 있는 최소한의 정점이 dfs_num[u]보다 작다면 u는 절단점일 수 가 없다. 왜냐하면 v에서 u를 거치지 않고 u의 상위 노드로 갈 수가 있기때문에 u가 사라지더라도 한개의 컴포넌트가 두개로 쪼개어 지지 않고 여전히 연결되어 있다는 것이다. 

  다시 말해서 현재 정점 u의 번호 dfs_num[u]가 u를 루트로 하는 스패닝 서브트리의 임의의 정점 v가 도달할 수 있는 최소한의 정점 dfs_low[v]보다 크지 않다면 u는 절단점이다. 

if dfs_num[u] <= dfs_low[v], then vertex, u is cut vertex(articulation point).

다리를 구하는 방법도 이와 약간 다를 뿐이다. 현재 정점 u의 dfs_num[u]가 dfs_low[v]보다 작다면 간선 (u, v)는 다리이이다.

if dfs_num[u] < dfs.low[v], then edge, (u, v) is bridge.

Code for this algorithm

void articulationPointAndBridge(int u) {

dfs_num[u] = dfs_low[u] = dfsNumberCounter++;

for(int i = 0; i < (int)AdjList[u].size(); ++i){

ii v = AdjList[u][i];    //typedef pari<int, int> ii;

if(dfs_num[v.first] == UNVISITED){

dfs_parant[v.first] = u;

if(u == dfsRoot) rootChildren++;

articulationPointAndBridge(v.first);

if(dfs_num[u] <= dfs_low[v.first])

articulation_vertex[u] = true;

if(dfs_num[u] < dfs_low[v.first])

bridge[u][v.first] = true;

dfs_low[u] = min(dfs_low[u], dfs_low[v.first]);

}

else if(dfs_parant[u] != v.first) 

dfs_low[u] = min(dfs_low[u], dfs_low[v.first]);

}    }

  위의 코드에서는 루트에 대한 예외를 따로 두지 않았다. 정점 u가 루트일 때에는 우리가 위에서 고려한 조건에 추가 적으로 루트의 자식이 두개이상일때 루트는 절단점이 된다. 그러므로 위의 함수외 부의 main함수 내부에 아래와 같은 코드를 추가한다.

articulation_vertex[root] = (rootChildren > 1);

또 다른 방법으로는 함수 내부에 코드를 변환 하는것도 가능한데 이는 DFS가 한번 호출될때 마다 절단점의 여부를 고려하는 if문의 조건절에 한개의 조건이 더 들어가는 셈이기때문에 외부에 서 예외를 처리하는 경우보다 더 높은 오버헤드를 초래한다.