타잔(Tarjan) 알고리즘

틀린점이나 이상한점  질문 등이 있을경우 아래 댓글로 알려주시면 감사하겠습니다.

 

타잔 Tarjan

 

 

 

 타잔 알고리즘은 SCC 를 찾는 알고리즘이다.

 

SCC란?  (Strong Connection Component) 강결합 컴포넌트 

간단하게 서로 연결되어있는 순한 노드끼리 묶어준다고 생각하면 쉽다.

 

 

크게 두개의 알고리즘이 있다고 볼수있는데

코사라주 알고리즘과 타잔 알고리즘이다.

 

이번엔 타잔 알고리즘을 설명하려 한다.

 

 

맨 아래에는 pc로 접속시(모바일은 사용불가) 코드를 눈으로 보며 생각과 맞는지 확인해볼수 있으니

본문을 읽어본뒤 테스트를 해보자.

 

 

 

알고리즘의 큰틀을 먼저 이해하면 구현자체는 쉽게 할수있다.

 

타잔알고리즘의 순서는

 

우선 함수 전 

 

count = 노드번호와 상관없이 노드를 처음탐색했을경우  탐색 번호를 의미한다.

lowset[]       = ( count  ) 를 넣어두는 배열 이며 비교할때 쓰인다.  그래프의 노드 사이즈와 같은 크기를 가지고 있다.

visit[]           = 노드 의 초기 (노드 카운터)를 넣어두는 배열 

 

 Tarjan 알고리즘 함수를 정의한다. 
    1. 노드 카운터를 증가시키고 현재 노드를 방문한 것으로 표시한다.
    2. 현재 노드를 스택에 푸시한다.
    3. 현재 노드의 이웃을 반복하며 방문한다
        a. 이웃이 아직 방문되지 않았다면, 재귀적으로 Tarjan 알고리즘을 호출한다.
        b. 이웃이 scc가 이미 되어있을경우 다시 돌아온다.

        c. 이웃의 노드 카운트와 lowset(내부의 count ) 값 을 비교후 작은값을  lowset  에 업데이트한다.
    4. 만약 방문할 노드가 없고 lowset[node] 값 이 현재 visit[node] 와 같다면, 강한 연결 요소(SCC) 발견 되었다.:
        a. SCC를 저장할 임시 벡터를 만든다.
        b. 현재 노드에 도달할 때까지 스택에서 노드를 팝하고, SCC 저장.
        c. SCC 벡터를 주요 SCC 벡터에 추가합니다.

 

예시를 들어

아래와 같은 그래프가 존재한다.

DFS로 하나씩 하나씩 들어가본다면

 

1->2->3->4->5

stack 1,2,3,4,5

5까지 도착한뒤 5에서 다시 연결되어있던 4로 돌아간다

위 이미지 처럼 이동한뒤 4->5 다시 5에 연결되어있던 4로 이동 한다.  

4의 경우 이미 방문했던 노드이기때문에   

두개의 node count 를 비교해준다

 

4노드가 들고있는 count  4 
5노드가 들고있는 count  5

 

가장 작은 노드인 4를 가져온다.

 

그렇다면

node   [1][2][3][4]   [5]    [6]

count  [1][2][3][4][5 > 4][x]

4번 확인뒤 5번은 방문할 노드가 없기때문에 4번노드로 돌아온다(DFS)

 

4->6번노드 방문시 5 번 노드와 같이

 

node   [1][2][3][4][5]   [6]

count  [1][2][3][4][4][6 > 4]

 

이후  더이상 갈수있는 노드가 없다.

 

들고있는 lowset[node] 값과 현재의 노드visit[node]의  값이 같은경우

stack 을 현재 노드까지  빼준다

stack [1,2,3,4,5,6] 

         [1][2][3][4][5][6]
 num = 4

 

stack[1,2,3] 

scc[0] = {6,5,4}

scc 묶음이 생겼다 

 

 

stack  {1,2,3}

 

4에서 돌아온뒤 노드 3번을 마저 탐색한다.

노드 1방문(이미 방문했던 노드)=> 더 작은노드 1 < 3 = 1을반환한다. 

num  = 1

  

작은값 갱신후 3번 노드 에서 더이상 갈수있는 노드가 없다. 

 

더작은 값을 을 num에 넣으며 현재 node 와 비교해주며 1번 노드까지 리턴되어 돌아온다

그럼 num  =1 

stack[1,2,3]

 

1 까지 stack을 빼준다.

 

CSS{{6,5,4},{3,2,1}}

 

 

코드로 보도록 하자.

 

코드는 두가지로  준비를 해두었다. low 값을 vector 로 저장하는 방법과

 

먼저 보이는 코드는 위 설명처럼 배열을 사용한다.

 

그 아래 코드는 가장 작은 값을 전달하는 식으로 만들어진 코드다.

 

두개의 큰 틀은 비슷하니 두개다 보면 이해가 쉬울수있다.

 

코드 1 

class TarjanSCC {
public:
    TarjanSCC(int nodes) : n(nodes), index(0), sccCount(0) {
        visit.resize(n, -1);
        lowset.resize(n, -1);
        onStack.resize(n, false);
    }

    void addEdge(int from, int to) {
        graph[from].push_back(to);
    }

    vector<vector<int>> findSCCs() {
        for (int i = 0; i < n; ++i) {
            if (visit[i] == -1) {
                tarjan(i);
            }
        }
        return sccs;
    }

private:
    int tarjan(int v) {
        visit[v] = index;
        lowset[v] = index;
        index++;
        stackNode.push(v);
        onStack[v] = true;

        for (int w : graph[v]) {
            if (visit[w] == -1) {
                lowset[v] = min(lowset[v], tarjan(w));
            } else if (onStack[w]) {
                lowset[v] = min(lowset[v], visit[w]);
            }
        }

        if (lowset[v] == visit[v]) {
            vector<int> scc;
            int w;
            do {
                w = stackNode.top();
                stackNode.pop();
                onStack[w] = false;
                scc.push_back(w);
            } while (w != v);
            sccs.push_back(scc);
            sccCount++;
        }
        return lowset[v];
    }

    int n;
    int index;
    int sccCount;
    unordered_map<int, vector<int>> graph;
    vector<int> visit;
    vector<int> lowset;
    vector<bool> onStack;
    stack<int> stackNode;
    vector<vector<int>> sccs;
};

 

 

코드 2

#include<algorithm>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;

stack<int> stackNode;
vector<bool> lowset;
vector<int> visit;
int nodecount = 0;
unordered_map<int, vector<int>> umap;
vector< vector<int>> scc;


int tajan(int index) {
	int num = 0;
	num = ++::nodecount;
	visit[index] = num;

	stackNode.push(index);
	for (int next : umap[index]) {
		if (visit[next] == -1) {
			num = min(tajan(next), num);
		}
		else if (lowset[next] == false) {
			num = min(visit[next], num);
		}
	}

	if (num == visit[index]) {
		vector<int> scc_temp;
		while (1) {
			int data = stackNode.top();
			stackNode.pop();
			lowset[data] = true;
			scc_temp.push_back(data);

			if (num == visit[data]) break;
		}
		sort(scc_temp.begin(), scc_temp.end());
		scc.push_back(scc_temp);
	}

	return num;
}

 

 

아래 시각화 도구로 확인해보자.

 

*그래프가 엉켜서 보기가 힘들다면*  클릭해서 노드 위치를 움직일수 있으니 보기 편하게 만든뒤 보면 보기 편하다

타잔 알고리즘 단계별 시각화 도구

노드 수: 간선 수: 양방향 간선 포함: