브리지(Bridge)란 무엇인가?
무방향 그래프(undirected graph)에서 브리지(bridge, 다리)는 해당 간선을 제거했을 때 그래프의 연결이 끊어지거나, 하나의 그래프가 서로 다른 컴포넌트(component)로 분리되는 간선을 의미합니다.
실제 네트워크 관점에서 생각해 보면, 네트워크에 브리지 역할을 하는 연결이 존재하고 그 연결이 끊어진다면 전체 네트워크가 마비될 수 있습니다. 따라서 네트워크의 안정성을 평가하거나 취약한 병목 지점을 찾을 때 브리지를 식별하는 작업이 매우 중요합니다.
입력과 출력
입력: 그래프의 인접 행렬(adjacency matrix) 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 출력: 주어진 그래프의 브리지: Bridge 3--4 Bridge 0--3
알고리즘: DFS 기반 브리지 탐색
브리지는 깊이 우선 탐색(DFS)을 활용하면 O(V+E)의 시간 복잡도로 효율적으로 찾을 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- disc[]: 각 정점이 처음 발견(discovery)된 시간을 저장합니다.
- low[]: 해당 정점 또는 그 서브트리에서 도달할 수 있는 가장 작은 발견 시간을 저장합니다.
- 자식 정점 v에 대해 low[v] > disc[start] 조건이 성립하면, v의 서브트리 어디에서도 start보다 먼저 방문한 정점으로 돌아갈 수 없다는 뜻이므로 start--v 간선은 브리지입니다.
bridgeFind(start, visited, disc, low, parent)
입력 − 시작 정점(start), 노드 방문 여부를 표시하는 visited 배열, 정점의 발견 시간을 담는 disc 배열, 서브트리 정보를 담는 low 배열, 현재 정점의 부모를 저장하는 parent 배열
출력 − 브리지가 발견되면 화면에 출력
Begin
time := 0 // time 값은 다음 함수 호출 시 초기화되지 않음
start를 방문 처리
disc[start] := time + 1, low[start] := time + 1
time := time + 1
그래프 G의 모든 정점 v에 대해 반복:
(start, v) 사이에 간선이 존재하면:
v를 아직 방문하지 않았다면:
parent[v] := start
bridgeFind(v, visited, disc, low, parent)
low[start] := low[start]와 low[v] 중 최솟값
만약 low[v] > disc[start]라면:
start에서 v로 가는 브리지 출력
그렇지 않고 v가 start의 부모가 아니라면:
low[start] := low[start]와 disc[v] 중 최솟값
반복 종료
End
C++ 예제 코드
#include<iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
int min(int a, int b) {
return (a<b)?a:b;
}
void bridgeFind(int start, bool visited[], int disc[], int low[], int parent[]) {
static int time = 0;
visited[start] = true; // 시작 정점을 방문 처리
disc[start] = low[start] = ++time; // 발견 시간(disc)과 low 값 초기화
for(int v = 0; v<NODE; v++) {
if(graph[start][v]) { // start와 연결된 모든 정점 v에 대해
if(!visited[v]) {
parent[v] = start; // start를 부모 노드로 지정
bridgeFind(v, visited, disc, low, parent);
// v의 서브트리가 start의 부모 쪽과 연결될 수 있는 경우 low 갱신
low[start] = min(low[start], low[v]);
if(low[v] > disc[start])
cout << "Bridge " << start << "--"<<v<<endl;
} else if(v != parent[start]) // 재귀 호출 이전 상태를 위해 low 갱신
low[start] = min(low[start], disc[v]);
}
}
}
bool bridges() {
bool *vis = new bool[NODE];
int *disc = new int[NODE];
int *low = new int[NODE];
int *parent = new int[NODE];
for(int i = 0; i<NODE; i++) {
vis[i] = false; // 아직 어떤 노드도 방문하지 않음
parent[i] = -1; // 초기에는 모든 노드에 부모가 없음
}
for(int i = 0; i<NODE; i++)
if(!vis[i]) // 방문하지 않은 노드가 있다면 그래프가 연결되어 있지 않은 것
bridgeFind(i, vis, disc, low, parent);
}
int main() {
cout << "Bridges in given graph:"<<endl;
bridges();
}
실행 결과
Bridges in given graph: Bridge 3--4 Bridge 0--3
마치며
위 예제에서 정점 3과 4를 잇는 간선, 그리고 정점 0과 3을 잇는 간선이 브리지로 검출되었습니다. 두 간선 중 하나라도 제거되면 그래프가 분리되기 때문입니다. 이처럼 브리지 찾기 알고리즘은 통신망 설계, 전력망 분석, 소셜 네트워크 구조 분석 등 연결성이 중요한 다양한 분야에서 활용될 수 있으며, DFS 한 번의 순회만으로 모든 브리지를 찾을 수 있어 매우 효율적입니다.