이 프로그램은 그래프의 에지 연결성(Edge Connectivity), 즉 브리지(Bridge)를 찾는 방법을 다룹니다. 브리지란 그래프에서 해당 간선을 제거했을 때 그래프가 연결이 끊어지는(disconnected) 간선을 의미합니다. 무방향 그래프에서 브리지를 하나 제거하면 연결 요소(connected component)의 개수가 증가하게 됩니다.
이 알고리즘은 DFS(깊이 우선 탐색)를 기반으로 하며, 각 정점의 발견 순서(disc)와 도달 가능한 가장 낮은 정점(low) 값을 이용해 브리지를 효율적으로 판별합니다.
함수 및 의사코드
Begin
함수 connections()는 재귀적으로 호출되어 연결(브리지)을 찾습니다:
A) 현재 노드를 방문 처리(visited)합니다.
B) 시간(disc)과 low 값을 초기화합니다.
C) 현재 노드에 인접한 모든 정점을 순회합니다.
D) x를 루트로 하는 서브트리가 w의 조상 중 하나와 연결되어 있는지 확인합니다.
x 서브트리에서 도달 가능한 가장 낮은 정점이 DFS 트리에서 w보다 아래에 있다면,
w-x는 브리지입니다.
E) 부모 함수 호출을 위해 w의 low 값을 갱신합니다.
End
Begin
함수 Con()은 connections()를 활용합니다:
A) 모든 정점을 미방문 상태로 표시합니다.
B) par, visited 배열과 connections 관련 변수를 초기화합니다.
C) 그래프 내 간선들 사이의 브리지를 출력합니다.
End예제 코드
#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 서브트리에서 도달 가능한 가장 낮은 정점이
// DFS 트리에서 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;
}출력 결과
첫 번째 그래프의 브리지 2 3 1 2 1 4 0 1
위 출력에서 확인할 수 있듯이, 프로그램은 주어진 그래프에서 제거 시 연결이 끊어지는 간선들, 즉 브리지들을 성공적으로 찾아냅니다. 이 알고리즘은 DFS를 한 번만 수행하므로 시간 복잡도는 O(V + E)로 매우 효율적입니다.