그래프 이론에서 단절점(Articulation Point)은 해당 정점과 그 정점에 연결된 간선들을 제거했을 때 그래프가 둘 이상의 조각으로 분리되는 정점을 의미합니다. 연결되지 않은 무방향 그래프에서는, 특정 정점을 제거했을 때 연결 요소(Connected Component)의 개수가 증가한다면 그 정점이 단절점이 됩니다.
알고리즘
단절점을 찾기 위해 깊이 우선 탐색(DFS)을 활용합니다. DFS 트리에서 정점 w가 단절점이 되는 조건은 다음 두 가지 중 하나를 만족하는 경우입니다.
- w가 DFS 트리의 루트이면서, 자식 노드를 두 개 이상 가지고 있는 경우
- w가 루트가 아니면서, w를 루트로 하는 서브트리 내 어떤 정점도 w의 조상으로 향하는 백 에지(Back Edge)를 갖지 않는 경우
C++ 구현 예제
#include<iostream>
#include <list>
#define N -1
using namespace std;
class G {
int n;
list<int> *adj;
// 함수 선언
void APT(int v, bool visited[], int dis[], int low[],
int par[], bool ap[]);
public:
G(int n); // 생성자
void addEd(int w, int x);
void AP();
};
G::G(int n) {
this->n = n;
adj = new list<int>[n];
}
// 그래프에 간선 추가
void G::addEd(int w, int x) {
adj[x].push_back(w); // v의 리스트에 u 추가
adj[w].push_back(x); // u의 리스트에 v 추가
}
void G::APT(int w, bool visited[], int dis[], int low[], int par[], bool ap[]) {
static int t=0;
int child = 0; // DFS 트리에서의 자식 수 초기화
// 현재 노드를 방문 처리
visited[w] = true;
dis[w] = low[w] = ++t;
list<int>::iterator i;
// 인접한 모든 정점 탐색
for (i = adj[w].begin(); i != adj[w].end(); ++i) {
int x = *i; // x는 현재 인접 정점
if (!visited[x]) {
child++;
par[x] = w;
APT(x, visited, dis, low, par, ap);
low[w] = min(low[w], low[x]);
// 다음 경우에 w는 단절점이 됩니다 :
// w가 DFS 트리의 루트이고 자식이 두 개 이상인 경우
if (par[w] == N && child> 1)
ap[w] = true;
// w가 루트가 아니고, 자식의 low 값이 w의 발견 순서(dis) 값보다 크거나 같은 경우
if (par[w] != N && low[x] >= dis[w])
ap[w] = true;
} else if (x != par[w]) // low 값 갱신
low[w] = min(low[w], dis[x]);
}
}
void G::AP() {
// 모든 정점을 미방문 상태로 표시
bool *visited = new bool[n];
int *dis = new int[n];
int *low = new int[n];
int *par = new int[n];
bool *ap = new bool[n];
for (int i = 0; i < n; i++) {
par[i] = N;
visited[i] = false;
ap[i] = false;
}
// 정점 'i'를 루트로 하는 DFS 트리에서 단절점을 찾기 위해 APT() 호출
for (int i = 0; i < n; i++)
if (visited[i] == false)
APT(i, visited, dis, low, par, ap);
// 단절점 출력
for (int i = 0; i < n; i++)
if (ap[i] == true)
cout << i << " ";
}
int main() {
cout << "\n첫 번째 그래프의 단절점 \n";
G g1(5);
g1.addEd(1, 2);
g1.addEd(3, 1);
g1.addEd(0, 2);
g1.addEd(2, 3);
g1.addEd(0, 4);
g1.AP();
return 0;
}실행 결과
첫 번째 그래프의 단절점 0 2
위 예제에서 정점 0과 2를 제거하면 그래프가 분리되므로, 두 정점이 단절점임을 확인할 수 있습니다. 이 알고리즘은 Tarjan의 단절점 찾기 알고리즘에 기반하며, DFS를 한 번만 수행하므로 시간 복잡도는 O(V+E)입니다.