파이썬: Tarjan 알고리즘 (Strongly Connected Components)

Tarjan's Algorithm

Tarjan's strongly connected components algorithm

 

1. 소개

타르잔 알고리즘은 Kosaraju 알고리즘처럼

방향 그래프에서 strongly connected component들을 찾아내는 더 나은 알고리즘이다.

(코사라주는 DFS 2개, 타르잔은 DFS 1개를 이용해 linear하게 찾을 수 있음)

 

(Airport Connections와 같은 문제에서 사용할 수 있다.)

@filipyoo

 

아래는 William Lin이라는 고등학생 학생과 algoexpert CEO가 구글 모의 인터뷰를 하는 영상이다.

William Lin은 미국 올림피아드 대회에서 금메달을 받을 만큼 C++ 코딩 실력이 엄청 뛰어난 인물이고,

아래 영상에선 코사라주 알고리즘을 이용해서 문제를 풀었다.

 

Google Coding Interview With A High School Student @유튜브 링크

 

2. Strongly Connected Component

강 결합 컴포넌트(SCC)는 방향(Directed) 그래프에서,

아래 사진처럼 서로서로 오고 갈 수 있는 노드(들)의 모음이다.

(아래는 총 4개의 SCC를 가진 그래프)

@WilliamFiset Youtube

 

3. Tarjan 알고리즘

 

low-link 값

DFS 할 때 자기 자신을 포함해서, 도달할 수 있는 노드 id가 가장 작은 값이다.

아래 예를 들면,

노드 1은 [1 -> 6 -> 0, 1 -> 4, 1 -> 2] 중 0이 가장 작은 노드 id 값이므로, low-link = 0

노드 3은 [3 -> 2, 3 -> 4, 3 -> 5] 중 가장 작은 노드 id 값은 2이므로, low-link = 2

@WilliamFiset Youtube

 

위 사진처럼 노드 선택만 잘되면 한 번에 SCC를 찾아낼 수 있지만,

아래처럼 노드 선택을 잘못하면, 모두 low-link 값이 같아 구별할 수가 없다.

 

모두 low-link = 0 @WilliamFiset Youtube

 

여기서, Tarjan 알고리즘이 나설 차례이다.

1. stack에 노드를 추가한다.
2. u와 v가 그래프에 있고, 현재 u 노드를 탐색 중이라면
3. u의 low-link 값은 자기 자신 값과, v의 low-link 값 중 작은 값이며
4. stack에 있다면 u의 low-link 값은 v 노드 id 값 중 작은 값이다.

 

코드를 보면 좀 더 이해가 쉬울 것이다.

 

4. 파이썬

@WilliamFiset Youtube

위 노드 0부터 시작해서 dfs 하는 순서대로 노드 id 값을 부여했다.

 

from collections import defaultdict

UNVISITED = -1  # constant


class Graph:
    global UNVISITED

    def __init__(self, vertices):
        self.v = vertices
        self.g = defaultdict(list)
        self.id = 0

    def addEdge(self, u, v):
        self.g[u].append(v)

    # 메인 알고리즘
    def findSCCs(self):
        ids = [UNVISITED] * self.v  # 노드 수만큼 -1
        low = [UNVISITED] * self.v  # 노드 수만큼 -1

        onStack = [False] * self.v  # 노드 수만큼 False
        stack = []  # dfs

        for i in range(self.v):
            if ids[i] == UNVISITED:  # 노드 i가 처음이면 dfs
                self.dfs(i, low, ids, onStack, stack)
                
        return low  # low-link 값이 같은 것끼리 SCC를 만든다.

    # 깊이 우선 탐색
    def dfs(self, at, low, ids, onStack, stack):
        ids[at] = self.id
        low[at] = self.id
        self.id += 1  # id 부여

        onStack[at] = True  # 현재 노드 visited
        stack.append(at)

        for to in self.g[at]:
            if ids[to] == UNVISITED:  # 처음 사용하는 노드라면
                self.dfs(to, low, ids, onStack, stack)  # 연결된 노드로 dfs
                low[at] = min(low[at], low[to])  # low-link 업데이트
            elif onStack[to] == True:  # 스택에 있으면
                low[at] = min(low[at], ids[to])  # low-link 업데이트

        # SCC 결과 출력하기
        w = UNVISITED
        if low[at] == ids[at]:
            print("Strongly Connected Components: ", end="")
            while w != at:
                w = stack.pop()
                print(f"Node {w}", end=" ")
                onStack[w] = False
            print()

    def __str__(self):
        return self.print()

    def print(self):
        for vertice, edge in self.g.items():
            print(f"{vertice} ->", *edge)


if __name__ == "__main__":
    g = Graph(8)  # 8 vertices
    g.addEdge(0, 1)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(3, 4)
    g.addEdge(3, 7)
    g.addEdge(4, 5)
    g.addEdge(5, 0)
    g.addEdge(5, 6)
    g.addEdge(6, 0)
    g.addEdge(6, 2)
    g.addEdge(6, 4)
    g.addEdge(7, 3)
    g.addEdge(7, 5)

    # g.print()
    g.findSCCs()


""" 결과

Strongly Connected Components: Node 2 Node 1 Node 0 
Strongly Connected Components: Node 6 Node 5 Node 4 
Strongly Connected Components: Node 7 Node 3 

"""

 

참고

아래 영상이 제일 설명이 괜찮은 것 같다.

WilliamFiset의 Tarjan 알고리즘과 SCC 설명 (영문) @유튜브 링크