[JS] 타잔 알고리즘

1. 강한 결합 요소(SCC, Stongly Connected Component)

 강한 결합 요소란 유향 그래프 안에서 강하게 결합된 정점 집합을 의미한다. 서로 긴밀하게 연결되어있기 때문에 강한 결합 요소라고 하며, SCC 알고리즘이라고 불린다. 좀 더 쉽게 설명하자면, 싸이클(원형 그래프)를 생각하면 되는데, 두 가지 조건을 만족해야 한다.

 

 

1. 임의의 유향 그래프 내 정점 A, B 사이에 경로가 항상 존재해야한다.

2.  A에서 B로 가는 경로, B에서 A로 가는 경로가 동시에 존재할 수 없다.

 

 

 [그림 1]을 보면 충분히 SCC인지 아닌지 판별할 수 있다.

 

[그림 1] 강한 결합 요소 구별

 

 왼쪽 섹션에 있는 그림은 조건 1, 2를 둘 다 만족하고 있으므로 강한 결합 요소다. 하지만 오른쪽 두 그림은 두 점을 지나는 경로가 존재하기 때문에 강한 결합 요소가 아니다. 강한 결합 요소가 유향그래프라는 전제조건이 붙은 이유가 조건 2 때문이다.

 

 

2. 타잔 알고리즘

 강한 결합 요소를 추출하는 알고리즘은 코사리주 알고리즘, 타잔 알고리즘이 있다. 일반적으로 코사리주 알고리즘이 구현이 더 쉽다 한다. 하지만 이번 포스팅에서는 적용이 쉬운 타잔 알고리즘에 대해서 포스팅을 하도록 하겠다. 타잔 알고리즘은 1972년에 로버트 타잔이 만든 알고리즘이며 SCC 한 개를 찾아낼 때 한 번의 깊이 우선 탐색을 거치면서 방문한 노드를 스택에 저장하면서 강한 결합 요소를 찾는 알고리즘이다. 이제부터 그림을 이용하여 타잔 알고리즘이 어떤 프로세스를 갖고 있는지를 설명하도록 하겠다.

 

 

 [그림 2]는 타잔 알고리즘을 수행하기 전에 필요한 준비물을 그림으로 나타낸 것이다.

 

[그림 2] 타잔 알고리즘 구현 준비물

 

isFinished: 강한 결합 요소 찾는 작업 유무 판별(T: 작업 완료, F: 진행 중)

isVisit: 깊이 우선 탐색 시 방문 노드 체크(T: 방문 완료, F: 아직 방문 X)

 

 

 먼저, 1을 시작으로 깊이 우선 탐색을 하고 정점 1을 스택에 넣는다. 이 과정에서 각 방문한 정점 노드에 부모 노드를 설정해야 하는데, 일단 부모노드를 자기자신으로 설정한다.

 

[그림 3] 타잔 알고리즘 1 단계

 

 이제 1을 시작으로 부모 노드 값을 리턴하는 재귀 호출을 이용해서 깊이 우선 탐색을 한다.

 

[그림 4] 타잔 알고리즘 2 단계

 

 3과 연결된 정점은 1이다. 하지만 1은 이미 방문한 노드이기 때문에, 강한 결합 요소 작업 완료 유무를 검사한다. 정점 1은 아직 진행 중 상태이다. 이로써 우리는 정점 1, 2, 3은 한 방향 싸이클을 형성하고있고, 정점 3의 부모노드는 정점 1이라는 것을 알게된다. 따라서 최종 부모노드인 1 값을 반환하도록 한다. 그리고나서 재귀 호출 스택에 쌓인 정점들을 반환한다. 반환하면서 저장된 부모노드 값과 최종 부모노드 1을 비교해서 더 작은 값을 반환한다. 조건은 최종 반환 노드 값 1과 반환된 정점 값이 같을 때 까지다. 이 과정이 끝난 후의 정점 값과 부모노드 값은 1로 같다.  이 때 스택에 있는 정점들을 부모노드 값 1과 같을 때까지 Pop 해준다. 이 때 Pop을 해준 정점들이 강한 결합 요소 관계를 갖게 되므로, 정점에 맞는 isFinished에 작업이 완료되었다는 True 값을 주도록하자.

 

[그림 5] 타잔 알고리즘 3 단계

 

 여태 까지의 과정을 모든 작업이 완료 될 때까지 반복을 해주면, SCC는 [1,2,3], [5,7,6], [4] 로 총 3개가 나오게 된다.

 

 

 프로그램은 다음과 같다.

const graph = [
  0,        //  vertex: none
  [2],      //  vertex: 1 
  [3],      //  vertex: 2
  [1],      //  vertex: 3
  [2,5],    //  vertex: 4
  [7],      //  vertex: 5
  [5],      //  vertex: 6
  [6]       //  vertex: 7
]

const isVisited = new Array(8).fill(false);
const isFinished = new Array(8).fill(false);
const stack = [];
const scc = [];

const dfs = function (vertex){
  let parent = vertex;
  isVisited[vertex] = true;
  stack.push(vertex);
  for(let i=0; i<graph[vertex].length; i++){
    const nextV = graph[vertex][i];
    if(!isVisited[nextV]){
      parent = Math.min(parent, dfs(nextV));
    }
    else if(!isFinished[nextV]){
      parent = nextV;
    }
  }

  if(parent === vertex){
    const sccEl = [];
    let topEl = 0;
    do{
      topEl = stack.pop();
      isFinished[topEl] = true;
      sccEl.unshift(topEl);
    }while(topEl !== parent);
    scc.push(sccEl);
  }

  return parent;
}

const tarjan = function(){
    let parent = 0;
    let topEl = 0;
    for(let vertex = 1; vertex<graph.length; vertex++){
      if(!isFinished[vertex]){
        dfs(vertex);
      }
    }
}

const main = (function(){
  tarjan();
  console.log("SCC List")
  for(let i=0; i<scc.length; i++)
    console.log(scc[i]);
}());

 

 

3. 참고 자료

• 26. 강한 결합 요소(Strongly Connected Component) - 안경잡이 개발자

• 강한 결합 요소 - 위키 백과

• SCC(Strongly Connected Component) - 자손 9319