Tarjan's algorithm

1. Problem

- 방향 그래프(directed graph)에서 SCC를 찾아보자.

- 강한 요소 결합(Strongly Connected Component, SCC)이란 그래프에 있는 노드 중에서 서로 도달이 가능한 노드들의 집합을 말한다.

- 쉽게 말하면, 그래프 안에서 사이클을 이루는 노드의 집합이다.

- 타잔 알고리즘은 정점에 대해 DFS(깊이 우선 탐색)을 실행하며 SCC를 찾는다.

 

2. Input

1) int[][] graph

- graph[i][j]는 i번 노드에서 j번 노드로 향하는 간선을 뜻한다.

2) static int vertex

- 그래프 내에 존재하는 노드의 수를 의미한다.

 

3. Output

1) SCC의 개수

2) 각 SCC에 속하는 노드의 번호를 출력

 

4. Example

// 각 노드를 방문하며 부모를 확인한다. 노드에 방문시 1부터 고유번호를 매긴다.
// 0번부터 시작한다.
    stack=[0], parent=[1,0,0,0,0,0,0]
// 0번과 연결된 1번을 스택에 넣는다.
    stack=[0,1], parent=[1,2,0,0,0,0,0]
// 1번과 연결된 2번을 스택에 넣는다.
    stack=[0,1,2], parent=[1,2,3,0,0,0,0]
// 2번과 연결된 0번이 현재 스택에 존재함을 알았다. 따라서 2번의 부모는 0번이 된다.
    stack=[0,1,2],  parent=[1,2,1,0,0,0,0]
// 1번의 부모는 2번에서 넘어온 0번이 된다.
    stack=[0,1,2], parent=[1,1,1,0,0,0,0]
// 0번의 부모는 1번에서 넘어온 0번이 되고, 0번은 자기가 해당 SCC의 부모임을 확인하게 된다.
    stack=[], scc=[[2,1,0]]
// 3번을 방문한다.
    stack=[3], parent=[1,1,1,4,0,0,0]
// 3번과 연결된 4번을 스택에 넣는다.
    stack=[3,4], parent=[1,1,1,4,5,0,0]
// 4번과 연결된 5번을 스택에 넣는다.
    stack=[3,4,5], parent=[1,1,1,4,5,6,0]
// 5번과 연결된 6번을 스택에 넣는다.
    stack=[3,4,5,6], parent=[1,1,1,4,5,6,7]
// 6번과 연결된 4번이 현재 스택에 존재함을 알았다. 따라서 6번의 부모는 4번이 된다.
    stack=[3,4,5,6], parent=[1,1,1,4,5,6,5]
// 5번의 부모는 6번에서 넘어온 4번이 된다.
    stack=[3.4,5,6], parent=[1,1,1,4,5,5,5]
// 4번의 부모는 5번에서 넘어온 4번이 되고, 4번은 자기가 해당 SCC의 부모임을 확인하게 된다.
    stack=[3], scc=[[2,1,0],[6,5,4]]
// 스택에 남은 3번도 SCC에 들어간다.
    stack=[], scc=[[2,1,0],[6,5,4],[3]]

 

5. Code

// 클래스 변수
static int vertex = 7; // 주어진 그래프의 정점의 개수
static int[] parent = new int[vertex]; // 부모 노드의 번호
static List<List<Integer>> scc = new ArrayList<List<Integer>>(); // SCC
static List<List<Integer>> edges = new ArrayList<List<Integer>>(); // 노드별 간선 정보
static Stack<Integer> stack = new Stack<>(); // dfs 수행 시 이용할 스택
static int id = 0; // 노드 방문시 붙여줄 고유번호. 1번부터 매긴다.
static boolean[] finished = new boolean[vertex]; // 처리가 완료됐다면 true

// main()
int[][] graph = {{0,1},{1,2},{2,0},{3,2},{3,4},{4,5},{5,6},{6,4}}; // 간선의 정보

for(int i=0 ; i<vertex ; i++) // 한 노드에 연결된 노드들을 더한다.
    edges.add(new ArrayList<>());
for(int i=0 ; i<graph.length ; i++)
    edges.get(graph[i][0]).add(graph[i][1]);

for(int i=0 ; i<vertex; i++) // 각 노드를 방문하며 dfs 수행
    if(parent[i]==0) dfs(i);

static int dfs(int n) {
    parent[n] = ++id; // 수행되는 순서대로 노드에 고유 번호를 매긴다.
    stack.push(n); // 스택에 노드 삽입

    int p = parent[n];
    for(int x : edges.get(n)) {
        if(parent[x]==0) // x가 방문하지 않았던 노드인 경우
            p = Math.min(p, dfs(x));
        else if(!finished[x]) // 방문은 했으나 스택에 있는 경우
            p = Math.min(p, parent[x]);
    }

    if(p==parent[n]) { // 자기 자신이 부모라는 것을 알았을 경우
        List<Integer> list = new ArrayList<>();
        while(true) {
            int x = stack.pop(); // 스택에서 노드를 꺼낸 후
            list.add(x);  // 리스트에 넣고
            finished[x] = true; // 처리 완료 작업을 한다.
            if(x==n) break; // 자기 자신에 도달하면 리스트 작성을 중단한다.
        }
        scc.add(list); // 작성한 리스트를 scc에 저장한다.
    }
    
    return p;
}

// 다시 main()
System.out.printf("SCC의 개수: %d\n", scc.size());
for(int i=0 ; i<scc.size(); i++) {
    System.out.printf("%d번째 SCC: ", i+1);
    for(int j=scc.get(i).size()-1 ; j>=0 ; j--) // scc에는 역순으로 저장되어있어서
        System.out.printf("%d,", scc.get(i).get(j)); // 맨 뒤부터 출력한다.
    System.out.println();
}
// 출력 결과
SCC의 개수: 3
1번째 SCC: 0,1,2
2번째 SCC: 4,5,6,
3번째 SCC: 3,

- 시간 복잡도는 O(V+E)를 따른다. V는 노드의 개수, E는 간선의 개수를 뜻한다.