그래프의 정점 연결성(Vertex Connectivity)을 구하려면 먼저 해당 그래프의 단절점(Articulation Points)을 찾아야 합니다. 그래프에서 단절점(또는 컷 버텍스, Cut Vertex)이란 그 정점과 연결된 간선들을 함께 제거했을 때 그래프 전체가 분리되어 버리는 정점을 의미합니다. 또한 비연결(disconnected) 무방향 그래프에서는, 특정 정점을 제거했을 때 연결 요소(connected component)의 개수가 증가한다면 그 정점이 단절점이라고 할 수 있습니다.
알고리즘
단절점을 찾기 위해 DFS(깊이 우선 탐색)를 활용합니다. DFS 탐색 과정에서 정점 w는 다음 두 조건 중 하나를 만족할 경우 단절점이 됩니다.
- w가 DFS 트리의 루트(root)이면서 자식 노드를 2개 이상 가지는 경우
- w가 루트가 아니면서, 자식 x에 대해 w를 루트로 하는 서브트리 내의 어떤 정점도 w의 조상(ancestor)으로 향하는 백 엣지(back edge)를 가지지 않는 경우
쉽게 말해, w 아래의 서브트리에 속한 모든 정점이 w를 거치지 않고는 위쪽 조상들과 연결될 수 없다면, w를 제거하는 순간 그래프가 끊어지므로 w는 단절점입니다.
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); //x의 리스트에 w 추가
adj[w].push_back(x); //w의 리스트에 x 추가
}
void G::APT(int w, bool visited[], int dis[], int low[], int
par[], bool ap[]) {
static int t=0;
int child = 0; //DFS 트리에서의 자식 수를 0으로 초기화
//현재 노드를 방문 처리
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 트리의 루트이면서 자식이 2개 이상인 경우
if (par[w] == N && child> 1)
ap[w] = true;
// w가 루트가 아니고, 자식 중 하나의 low 값이 w의 발견(discovery) 값 이상인 경우
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 << "\nArticulation points in first graph \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;
}실행 결과
Articulation points in first graph 0 2
실행 결과를 보면 첫 번째 그래프의 단절점은 0과 2입니다. 실제로 정점 0 또는 정점 2를 그래프에서 제거하면 나머지 정점들이 서로 연결되지 못하고 분리되는 것을 확인할 수 있습니다. 이처럼 DFS 기반의 단절점 탐색 알고리즘을 사용하면 그래프의 정점 연결성을 효율적으로 판별할 수 있습니다.