Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 그래프에서 브리지(다리) 간선 개수 찾는 방법

문제 개요

가중치가 없는 무방향 그래프에 n개의 정점과 m개의 간선이 주어져 있다고 가정해 봅시다. 그래프에서 브리지(Bridge, 다리) 간선이란 해당 간선을 제거했을 때 그래프가 연결 상태를 잃고 분리되는 간선을 의미합니다. 이 글에서는 주어진 그래프에 포함된 브리지 간선의 개수를 구하는 프로그램을 작성해 보겠습니다. 단, 그래프에는 평행 간선(parallel edge)이나 자기 루프(self-loop)는 존재하지 않는다고 가정합니다.

예를 들어 입력이 다음과 같다면,

n = 5, m = 6, edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}

출력은 1이 됩니다.

위 그래프에서 유일한 브리지 간선은 {2, 4}입니다. 이 간선을 제거하면 정점 4가 나머지 그래프와 분리되기 때문입니다.

해결 접근 방식: DFS 기반 브리지 찾기 알고리즘

이 문제는 깊이 우선 탐색(DFS)을 활용한 타잔(Tarjan)의 브리지 찾기 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • vk[v]: 정점 v가 DFS에서 발견된 순서(방문 시간)
  • l[v](low-link 값): v의 서브트리에서 역방향 간선을 통해 도달할 수 있는 가장 먼저 방문된 정점의 순서

간선 (v, x)에 대해 l[x] > vk[v]가 성립하면, x의 서브트리 어디에서도 v 또는 그 조상으로 돌아오는 경로가 없다는 뜻이므로 해당 간선은 브리지입니다.

알고리즘 단계

mSize := 100
크기가 mSize인 인접 리스트 배열 G 정의
2차원 배열 bridge 정의
크기가 mSize인 배열 visited, vk, l 정의
정수 쌍을 저장하는 edges 배열 정의

depthSearch(v, p = -1) 함수:
   visited[v] := 1
   vk[v] := l[v] := t++
   G[v]의 각 원소 x에 대해:
      x == p이면 다음 반복으로 건너뜀
      visited[x]가 참이면:
         l[v] := min(l[v], vk[x])
      아니면:
         depthSearch(x, v)
         l[v] := min(l[v], l[x])
         l[x] > vk[v]이면:
            bridge[v][x] := 1

bridgeSearch() 함수:
   t := 0
   i := 1부터 n까지:
      visited[i]가 거짓이면 depthSearch(i)

메인 로직:
   각 간선 (a, b)를 인접 리스트 G[a], G[b]에 양방향으로 추가
   bridgeSearch() 호출
   ans := 0
   i, j에 대해 i != j이고 bridge[i][j]가 참이면 ans 증가
   return ans

C++ 구현 예제

아래 구현 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

const int mSize = 100;
vector<int> G[mSize];
int n, m, t;
vector<vector<int>> bridge(mSize, vector<int>(mSize));
vector<int> visited(mSize);
vector<int> vk(mSize, -1), l(mSize, -1);
vector<pair<int, int>> edges;

void depthSearch(int v, int p = -1) {
    visited[v] = 1;
    vk[v] = l[v] = t++;
    for (auto x : G[v]) {
        if (x == p) {
            continue;
        }
        if (visited[x]) {
            l[v] = min(l[v], vk[x]);
        } else {
            depthSearch(x, v);
            l[v] = min(l[v], l[x]);
            if (l[x] > vk[v]) {
                bridge[v][x] = 1;
            }
        }
    }
}

void bridgeSearch() {
    t = 0;
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            depthSearch(i);
        }
    }
}

int solve() {
    for (int i = 0; i < m; ++i) {
        int a, b;
        a = edges[i].first;
        b = edges[i].second;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    bridgeSearch();
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j and bridge[i][j]) ans++;
        }
    }
    return ans;
}

int main() {
    n = 5, m = 6;
    edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}};
    cout << solve();
    return 0;
}

입력

5, 6, {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}

출력

1

마무리

이 알고리즘은 DFS를 한 번만 수행하므로 시간 복잡도는 O(V + E)로 매우 효율적입니다. 네트워크 안정성 분석, 통신망의 취약 지점 탐색 등 실제 문제에서도 브리지 간선 찾기는 널리 활용되는 중요한 그래프 이론 기법입니다.