이 글에서는 C++를 사용해 그래프의 최대 컷(maximum cut)을 찾는 방법을 다룹니다. 핵심은 그래프의 에지 연결성(edge connectivity)을 구하는 것으로, 이는 곧 브리지(bridge, 단절선)를 찾는 문제와 같습니다.
브리지란 그래프에서 해당 간선 하나만 제거해도 그래프가 둘 이상의 연결 요소로 분리되어 버리는 간선을 의미합니다. 즉, 무향 그래프에서 브리지를 제거하면 연결 요소(connected component)의 개수가 늘어나게 됩니다.
핵심 개념: 브리지(단절선)란?
무향 그래프에서 간선 (w, x)를 제거했을 때 w와 x가 더 이상 서로에게 도달할 수 없다면, 이 간선을 브리지라고 합니다. 브리지는 네트워크 설계나 통신망 안정성 분석에서 중요한 개념으로, 단일 장애점(single point of failure)처럼 네트워크 전체를 끊어버릴 수 있는 약점을 찾는 데 활용됩니다.
알고리즘 및 의사 코드
브리지를 찾는 대표적인 방법은 깊이 우선 탐색(DFS)을 활용한 타잔(Tarjan) 알고리즘입니다. 각 정점에 대해 다음 두 가지 값을 유지합니다.
- disc[] : DFS 탐색에서 해당 정점을 처음 발견한 순서(시간)
- low[] : 해당 정점의 서브트리에서 역방향 간선을 통해 도달할 수 있는 가장 작은 disc 값
탐색 중 low[x] > disc[w]가 성립하면, 정점 x 쪽에서 정점 w나 그 조상으로 돌아오는 경로가 없다는 뜻이므로 간선 w–x가 브리지입니다.
시작
함수 connections() : 브리지를 찾는 재귀 함수
A) 현재 노드를 방문 처리한다.
B) 시간(time) 값과 low 값을 초기화한다.
C) 현재 노드에 인접한 모든 정점을 순회한다.
D) x를 루트로 하는 서브트리가 w의 조상 중 하나와 연결되어 있는지 확인한다.
DFS 트리에서 x의 서브트리가 w보다 위의 정점(조상)에 도달하지 못하면 w–x는 브리지다.
E) 부모 함수 호출을 위해 w의 low 값을 갱신한다.
끝
시작
함수 Con() : connections()를 호출하는 드라이버 함수
A) 모든 정점을 미방문 상태로 표시한다.
B) par(부모), visited(방문 여부) 등 필요한 배열을 초기화한다.
C) 그래프의 모든 간선 중 브리지를 출력한다.
끝
C++ 전체 예제 코드
#include<iostream>
#include <list>
#define N -1
using namespace std;
class G {
// 함수 선언
int n;
list<int> *adj;
void connections(int n, bool visited[], int disc[], int low[], int par[]);
public:
G(int n); // 생성자
void addEd(int w, int x);
void Con();
};
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::connections(int w, bool visited[], int dis[], int low[],
int par[]) {
static int t = 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]) {
par[x] = w;
connections(x, visited, dis, low, par);
low[w] = min(low[w], low[x]);
// x의 서브트리에서 도달 가능한 최저 정점이 w보다 뒤라면 w–x는 브리지
if (low[x] > dis[w])
cout << w << " " << x << endl;
}
else if (x != par[w])
low[w] = min(low[w], dis[x]);
}
}
void G::Con() {
// 모든 정점을 미방문으로 표시
bool *visited = new bool[n];
int *dis = new int[n];
int *low = new int[n];
int *par = new int[n];
for (int i = 0; i < n; i++) {
par[i] = N;
visited[i] = false;
}
// 브리지를 찾기 위해 connections() 호출
for (int i = 0; i < n; i++)
if (visited[i] == false)
connections(i, visited, dis, low, par);
}
int main() {
cout << "\n첫 번째 그래프의 브리지 \n";
G g1(5);
g1.addEd(1, 2);
g1.addEd(3, 2);
g1.addEd(2, 1);
g1.addEd(0, 1);
g1.addEd(1, 4);
g1.Con();
return 0;
}
주요 함수 설명
- G(int n) : 생성자로, 정점 개수 n만큼 인접 리스트 메모리를 동적으로 할당합니다.
- addEd(w, x) : 무향 그래프이므로 양방향으로 간선을 추가합니다.
- connections() : 재귀적으로 DFS를 수행하면서 브리지를 판별하고 출력하는 핵심 함수입니다.
- Con() : 방문 여부와 부모 배열을 초기화한 뒤, 모든 정점에 대해 connections()를 호출합니다.
실행 결과
첫 번째 그래프의 브리지 2 3 1 2 1 4 0 1
시간 복잡도
타잔 알고리즘은 각 정점과 간선을 한 번씩만 방문하므로 시간 복잡도는 O(V + E)이며, 추가로 사용하는 배열 때문에 공간 복잡도는 O(V)입니다. 따라서 큰 규모의 그래프에서도 효율적으로 브리지를 찾을 수 있습니다.