[알고리즘] 타잔(tarjan) 알고리즘

SCC(Stronly Connected Components)란?

• SCC (강한 결합 요소)란 그래프 내에서 강하게 결합된 정점들의 집합 이다.
• 강하게 결합되었다는 뜻은 같은 SCC 내의 두 정점은 서로 도달이 가능하다는 뜻이다.

타잔(tarjan) 알고리즘

• SCC를 추출하는 알고리즘은 크게 코사라주 알고리즘, 타잔 알고리즘이 존재한다.
• 그 중에 타잔 알고리즘은 구현이 어렵지만 적용이 쉽다는 측면에서 널리 사용된다.

알고리즘 개요

• 다음과 같은 정보들의 집합이 필요하다.

  • nodeId[n] : n번 노드에게 부여되는 ID (DFS 함수 수행되는 순서대로 증가하게 부여, 어떤 노드가 DFS를 먼저 수행했는지 확인하기 위한 정보)
  • Stack<N> : DFS 수행하며 각 노드 번호를 담을 스택 자료구조
  • finish[n] : 각 노드가 SCC에 포함되는지 여부

• 알고리즘의 수행과정은 다음과 같다.

  • 모든 노드에 대해 nodeId[n] = 0 (DFS 수행X)일 경우 다음 DFS(n)을 수행해준다.
  • nodeId[n]를 부여해준다. (DFS를 수행한 순서대로 증가하는 값)
  • 스택에 n번 노드를 넣어준다.
  • parent(부모노드) 정보에 nodeId[n]을 저장한다.
  • n번 노드와 연결된 모든 노드(next)에 대해 다음과정을 진행한다.
    - (방문하지 않은 노드인 경우) parent = Math.min(parent, DFS(next))
    - (방문했으며 SCC를 구성하지 않은 경우) parent = Math.min(parent, nodeId[next]))
  • parent가 여전히 nodeId[n] 이라면 (돌고 돌아 자기 자신으로 들어옴) SCC 만들어줌
    - 스택에서 자기 자신이 나올 때까지 원소들을 빼주고 해당 원소들을 하나의 SCC로 구성

알고리즘 구현

public static int tarjan(int n) {
        nodeId[n] = ++id;
        stack.push(n);

        int parent = nodeId[n];
        for (int i = 0; i < map.get(n).size(); i++) {
            int next = map.get(n).get(i);
            if (nodeId[next] == 0) parent = Math.min(parent, tarjan(next));
            else if (!finish[next]) parent = Math.min(parent, nodeId[next]);
        }

        //부모가 자기 자신일 때
        //스택에서 자기 자신이 나올때까지 pop해주고 하나의 scc로 묶어줌
        if (parent == nodeId[n]) {
            List<Integer> tmp = new ArrayList<>();
            while(true) {
                int cur = stack.pop();
                tmp.add(cur);
                finish[cur] = true;
                if (cur == n) break;
            }
            result.add(tmp);
        }
        return parent;
    }

출처 : https://blog.naver.com/ndb796/221236952158