C++로 그래프의 브리지 찾기 – 그래프 연결을 끊는 최소 간선 수 구하기

개요

이 프로그램은 그래프의 간선 연결성(Edge Connectivity), 즉 브리지(Bridge, 다리 간선)를 찾는 방법을 다룹니다. 브리지란 해당 간선을 제거했을 때 그래프가 연결 해제(disconnect)되는 간선을 의미합니다. 무방향 그래프에서 브리지를 하나 제거하면 연결 요소(connected component)의 개수가 증가하게 됩니다.

즉, 그래프 전체의 연결을 끊기 위해 잘라내야 하는 최소 간선을 찾는 문제이며, 이는 깊이 우선 탐색(DFS)과 low 값 계산을 통해 효율적으로 해결할 수 있습니다.

connections() 함수와 의사 코드

시작
    함수 connections()는 브리지를 찾기 위한 재귀 함수입니다:
    A) 현재 노드를 방문하지 않음으로 표시합니다.
    B) 시간(disc) 값과 low 값을 초기화합니다.
    C) 현재 정점에 인접한 모든 정점을 순회합니다.
    D) x를 루트로 하는 서브트리가 w의 조상 중 하나와 연결되어 있는지 확인합니다.
       x의 서브트리에서 도달할 수 있는 가장 낮은 정점이 DFS 트리상에서 w보다 아래에 있다면,
       w-x 간선은 브리지입니다.
    E) 부모 함수 호출을 위해 w의 low 값을 갱신합니다.
끝

Con() 함수의 의사 코드

시작
    connections()를 활용하는 함수 Con():
    A) 모든 정점을 방문하지 않음으로 표시합니다.
    B) par(부모), visited(방문 여부), disc, low 배열을 초기화합니다.
    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); //w를 x의 리스트에 추가
   adj[w].push_back(x); //x를 w의 리스트에 추가
}
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 트리를 구축하면서 각 정점의 disc 값(탐색 순서)과 low 값(해당 정점에서 역방향 간선을 통해 도달할 수 있는 가장 높은 조상의 disc 값)을 유지합니다. 자식 정점 x의 low 값이 부모 정점 w의 disc 값보다 크다는 것은 x의 서브트리에서 w 위쪽으로 올라갈 수 있는 우회 경로가 없다는 뜻이며, 따라서 w-x 간선이 브리지가 됩니다.

각 정점과 간선을 한 번씩만 방문하므로 시간 복잡도는 O(V + E)이며, 공간 복잡도는 정점 수 V에 비례하여 O(V)입니다.