[알고리즘] Tajan Algorithm. 타잔 알고리즘 SCC

 

/* 타잔 알고리즘 */

타잔 알고리즘은 강한 연결 요소 (SCC: Strongly Connected Components)를 찾는 데 사용되는 효율적인 알고리즘입니다.

 

SCC: 방향 그래프에서 모든 노드가 서로 연결되어 있는 부분 그래프를 의미합니다. 예를 들어, A → B → C → A와 같이 한 노드에서 다른 모든 노드로 도달할 수 있는 경우, 해당 노드 집합은 SCC로 간주됩니다.

 

이 알고리즘은 DFS(깊이 우선 탐색)를 기반으로 동작하며, 한 번의 DFS로 모든 SCC를 찾을 수 있어 시간 복잡도가 O(V + E)인 매우 효율적인 알고리즘입니다.

/* 핵심 개념 */

타잔 알고리즘은 DFS 탐색 중 두 가지 배열(ids, low)을 사용하여 SCC를 판별합니다.

1. ids 배열:
   • 각 노드가 DFS에서 방문된 순서를 저장합니다.
   • 노드가 처음 방문되면 해당 노드의 id가 부여됩니다.
2. low 배열:
   • 각 노드에서 도달할 수 있는 가장 낮은 DFS 순서를 기록합니다.
   • 이를 통해 노드가 현재 탐색 중인 SCC의 일부인지 확인할 수 있습니다.
3. 스택(stack)과 onStack 배열:
   • 탐색 중인 노드를 관리하기 위해 스택을 사용합니다.
   • 특정 노드가 현재 스택에 있는지 확인하려면 onStack 배열을 참조합니다.

/* 동작 과정 */

타잔 알고리즘의 주요 단계는 다음과 같습니다:

1. DFS 탐색:
   • 모든 노드에 대해 DFS를 수행하며, 방문 순서를 ids 배열에 저장합니다.
   • 탐색 중에는 각 노드의 low 값을 갱신합니다.
2. low 값 갱신:
   • 자식 노드의 low 값을 사용하여 부모 노드의 low 값을 업데이트합니다.
   • 스택에 있는 노드로 돌아가는 역방향 간선(back edge)을 통해 low 값을 더 낮출 수 있습니다.
3. SCC 추출:
   • 노드의 ids와 low가 동일하다면, 해당 노드는 SCC의 루트입니다.
   • 스택에서 노드를 하나씩 꺼내면서 SCC를 구성합니다.
4. SCC 저장:
   • 추출된 SCC는 리스트 형태로 저장됩니다.

 

아래는 타잔 알고리즘을 Java로 구현한 코드입니다.

 

import java.util.*;

public class TarjanSCC {
    private List<List<Integer>> graph;
    private List<List<Integer>> sccs;
    private int[] ids;
    private int[] low;
    private boolean[] onStack;
    private Stack<Integer> stack;
    private int id;

    public TarjanSCC(List<List<Integer>> connection) {
        this.graph = connection;
        int n = graph.size();
        this.sccs = new ArrayList<>();
        this.ids = new int[n];
        Arrays.fill(ids, -1);
        this.low = new int[n];
        this.onStack = new boolean[n];
        this.stack = new Stack<>();
        this.id = 0;

        // Run Tarjan's algorithm for each node
        for (int i = 0; i < n; i++) {
            if (ids[i] == -1) {
                dfs(i);
            }
        }
    }

    private void dfs(int at) {
        stack.push(at);
        onStack[at] = true;
        ids[at] = low[at] = id++;

        for (int to : graph.get(at)) {
            if (ids[to] == -1) {
                dfs(to);
                low[at] = Math.min(low[at], low[to]);
            } else if (onStack[to]) {
                low[at] = Math.min(low[at], ids[to]);
            }
        }

        if (ids[at] == low[at]) {
            List<Integer> scc = new ArrayList<>();
            while (true) {
                int node = stack.pop();
                onStack[node] = false;
                scc.add(node);
                if (node == at) break;
            }
            sccs.add(scc);
        }
    }
}