콘텐츠로 이동

$O(N+M)$에 그래프의 브리지 찾기

무방향 그래프가 주어집니다. 브리지는 제거했을 때 그래프를 비연결 상태로 만드는(더 정확히는 그래프의 연결 요소 개수를 증가시키는) 간선으로 정의됩니다. 주어진 그래프에서 모든 브리지를 찾는 것이 과제입니다.

비형식적으로 말하면 이 문제는 다음과 같습니다: 도로로 연결된 도시들의 지도가 주어졌을 때, 모든 "중요한" 도로, 즉 제거하면 어떤 도시 쌍 사이의 경로가 사라지게 되는 도로를 모두 찾으십시오.

여기서 설명하는 알고리즘은 깊이 우선 탐색에 기반하며 $O(N+M)$의 복잡도를 가집니다. 여기서 $N$은 그래프의 정점 개수이고 $M$은 간선 개수입니다.

온라인으로 브리지 찾기 글도 있다는 점에 유의하십시오 - 여기서 설명하는 오프라인 알고리즘과 달리, 온라인 알고리즘은 변화하는 그래프에서 모든 브리지의 목록을 유지할 수 있습니다(단, 변화의 유일한 유형이 새로운 간선의 추가라고 가정합니다).

알고리즘

그래프의 임의의 정점 $root$를 골라 그 정점에서 깊이 우선 탐색을 실행합니다. 다음 사실(증명하기 쉽습니다)에 주목하십시오:

  • DFS 도중 정점 $v$에서 시작하는 간선들을 살펴보고 있다고 합시다. 현재 간선 $(v, to)$는 정점 $to$와 DFS 순회 트리에서 그 자손들 중 어느 것도 정점 $v$ 또는 그 조상으로 향하는 역방향 간선을 갖지 않을 때, 그리고 그때에만 브리지입니다. 실제로 이 조건은 간선 $(v, to)$를 제외하면 $v$에서 $to$로 가는 다른 길이 없다는 것을 의미합니다.

이제 각 정점에 대해 이 사실을 효율적으로 확인하는 방법을 알아야 합니다. 깊이 우선 탐색으로 계산되는 "노드 진입 시각"을 사용하겠습니다.

그러면 $\mathtt{tin}[v]$를 노드 $v$의 진입 시각이라고 합시다. 배열 $\mathtt{low}$를 도입합니다. 이 배열에는 노드 $v$가 자기 자신 또는 자손으로부터 간선 하나로 도달할 수 있는, DFS 탐색에서 발견된 노드의 가장 이른 진입 시각을 저장합니다. $\mathtt{low}[v]$는 $\mathtt{tin}[v]$, 역방향 간선 $(v, p)$를 통해 노드 $v$와 연결된 각 노드 $p$의 진입 시각 $\mathtt{tin}[p]$, 그리고 DFS 트리에서 $v$의 직계 자손인 각 정점 $to$에 대한 $\mathtt{low}[to]$ 값들 중 최솟값입니다:

$$\mathtt{low}[v] = \min \left\{ \begin{array}{l} \mathtt{tin}[v] \\ \mathtt{tin}[p] &\text{ for all }p\text{ for which }(v, p)\text{ is a back edge} \\ \mathtt{low}[to] &\text{ for all }to\text{ for which }(v, to)\text{ is a tree edge} \end{array} \right\}$$

이제 정점 $v$ 또는 그 자손 중 하나에서 조상 중 하나로 향하는 역방향 간선이 존재한다는 것은, 정점 $v$가 $\mathtt{low}[to] \leq \mathtt{tin}[v]$를 만족하는 자식 $to$를 가진다는 것과 동치입니다. $\mathtt{low}[to] = \mathtt{tin}[v]$이면 역방향 간선은 $v$로 직접 향하고, 그렇지 않으면 $v$의 조상 중 하나로 향합니다.

따라서 DFS 트리의 현재 간선 $(v, to)$는 $\mathtt{low}[to] > \mathtt{tin}[v]$일 때, 그리고 그때에만 브리지입니다.

구현

구현에서는 세 가지 경우를 구별해야 합니다: DFS 트리에서 간선을 따라 내려가는 경우, 정점의 조상으로 향하는 역방향 간선을 발견한 경우, 그리고 정점의 부모로 돌아가는 경우입니다. 각 경우는 다음과 같습니다:

  • $\mathtt{visited}[to] = false$ - 이 간선은 DFS 트리의 일부입니다;
  • $\mathtt{visited}[to] = true$ && $to \neq parent$ - 이 간선은 조상 중 하나로 향하는 역방향 간선입니다;
  • $to = parent$ - 이 간선은 DFS 트리에서 부모로 되돌아가는 간선입니다.

이를 구현하려면 현재 노드의 부모 정점을 인자로 받는 깊이 우선 탐색 함수가 필요합니다.

다중 간선이 있는 경우에는 부모로부터 오는 간선을 무시할 때 주의해야 합니다. 이 문제를 해결하기 위해 부모를 한 번만 건너뛰도록 보장하는 플래그 parent_skipped를 추가할 수 있습니다.

void IS_BRIDGE(int v,int to); // some function to process the found bridge
int n; // number of nodes
vector<vector<int>> adj; // adjacency list of graph

vector<bool> visited;
vector<int> tin, low;
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    bool parent_skipped = false;
    for (int to : adj[v]) {
        if (to == p && !parent_skipped) {
            parent_skipped = true;
            continue;
        }
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v])
                IS_BRIDGE(v, to);
        }
    }
}

void find_bridges() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
}

메인 함수는 find_bridges이며, 필요한 초기화를 수행하고 그래프의 각 연결 요소에서 깊이 우선 탐색을 시작합니다.

함수 IS_BRIDGE(a, b)는 간선 $(a, b)$가 브리지라는 사실을 처리하는 함수로, 예를 들어 그 간선을 출력합니다.

parent_skipped 플래그 덕분에 이 구현은 정점과 그 부모 사이의 다중 간선을 처리할 수 있습니다. 정점에 진입할 때 사용한 DFS 트리 간선 하나만 건너뛰고, 추가로 있는 평행 간선은 역방향 간선으로 처리합니다. 또는 부모 정점 대신 정점에 진입할 때 사용한 간선의 인덱스를 dfs에 전달하는 방법도 있습니다(이 경우 모든 간선의 인덱스를 저장합니다).

연습 문제