강한 연결 요소 찾기: 타잔 알고리즘 완벽 분석

작성일 : 2024-06-13

강한 연결 요소 찾기: 타잔 알고리즘 완벽 분석

그래프 이론에서 강한 연결 요소(Strongly Connected Components, SCCs)는 아주 중요한 개념입니다. 강한 연결 요소는 방향 그래프에서 모든 정점들이 서로 도달 가능한 부분 그래프입니다. 이를 찾기 위해 다양한 알고리즘이 사용되지만, 그 중에서도 타잔 알고리즘(Tarjan's Algorithm)은 효율적이고 직관적입니다. 이번 글에서는 타잔 알고리즘의 기본 개념부터 코드 구현까지 상세하게 분석해보도록 하겠습니다.

타잔 알고리즘의 기본 원리

타잔 알고리즘은 DFS(Depth-First Search, 깊이 우선 탐색)를 기반으로 하며, 각 정점에 대해 두 가지 중요한 정보인 disc(discovery time, 발견 시간)와 low 값을 기록합니다. disc 값은 DFS가 처음으로 그 정점에 도달한 시간을 나타내고, low 값은 해당 정점 혹은 하위 트리에서 방문할 수 있는 가장 높은 정점의 disc 값을 저장합니다.

알고리즘의 큰 아이디어는 다음과 같습니다:

DFS를 통해 정점을 방문하며 disc와 low 값을 갱신합니다.
정점을 스택에 저장하며, 스택의 요소들이 잠정적인 SCC에 속하는지를 추적합니다.
DFS 탐색 중에 low 값이 자신의 disc 값과 같은 정점을 찾으면, 해당 정점은 하나의 SCC의 루트입니다. 스택에서 해당 SCC의 모든 정점을 추출합니다.

알고리즘의 의사 코드


plaintext
initialize disc[v] and low[v] for all v to -1
initialize stack as empty
initialize onStack[v] for all v to False

function tarjan(v):
    disc[v] = low[v] = time
    time += 1
    stack.append(v)
    onStack[v] = True

    for (v, w) in edges[v]:
        if disc[w] == -1:  # w is not visited
            tarjan(w)
            low[v] = min(low[v], low[w])
        else if onStack[w]:  # w is in stack, hence in the current SCC
            low[v] = min(low[v], disc[w])

    if low[v] == disc[v]:  # v is the root of an SCC
        while True:
            w = stack.pop()
            onStack[w] = False
            add w to current SCC
            if w == v: break
        output current SCC

for all v:
    if disc[v] == -1:
        tarjan(v)

타잔 알고리즘의 예제

아래는 타잔 알고리즘을 적용한 예제입니다. 이 예제에서 방향 그래프는 다음과 같습니다:


plaintext
  0 → 1 → 2 → 3 ↘
  ↑        ↘   ↙
  \
   4 → 5

Python 구현 예제


python
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.Time = 0

    def add_edge(self, v, w):
        self.graph[v].append(w)

    def SCCUtil(self, u, low, disc, stack_member, st):
        disc[u] = self.Time
        low[u] = self.Time
        self.Time += 1
        stack_member[u] = True
        st.append(u)

        for v in self.graph[u]:
            if disc[v] == -1:
                self.SCCUtil(v, low, disc, stack_member, st)
                low[u] = min(low[u], low[v])
            elif stack_member[v]:
                low[u] = min(low[u], disc[v])

        w = -1  # To store stack extracted vertices
        if low[u] == disc[u]:
            while w != u:
                w = st.pop()
                print(w, end=' ')
                stack_member[w] = False
            print()

    def SCC(self):
        disc = [-1] * self.V
        low = [-1] * self.V
        stack_member = [False] * self.V
        st = []

        for i in range(self.V):
            if disc[i] == -1:
                self.SCCUtil(i, low, disc, stack_member, st)

# Driver code
if __name__ == '__main__':
    g1 = Graph(7)
    g1.add_edge(0, 1)
    g1.add_edge(1, 2)
    g1.add_edge(2, 0)
    g1.add_edge(1, 3)
    g1.add_edge(3, 4)
    g1.add_edge(4, 5)
    g1.add_edge(5, 6)
    g1.add_edge(6, 4)
    print('Strongly Connected Components in given graph:')
    g1.SCC()

설명

이 예제에서는 Graph 클래스를 정의하여 그래프를 표현하고, SCCUtil 메서드를 통해 각 정점에서 SCC를 찾습니다. SCC 메서드는 DFS를 시작하며, 아직 방문되지 않은 정점들을 대상으로 합니다.

타잔 알고리즘의 시간 복잡도

타잔 알고리즘의 시간 복잡도는 O(V + E)입니다. 여기서 V는 그래프의 정점 수, E는 그래프의 간선 수입니다. 이 알고리즘은 DFS를 기반으로 하기 때문에, 각 정점을 처음으로 방문하고, 다시 돌아올 때까지의 모든 간선을 확인합니다.

결론

타잔 알고리즘은 강한 연결 요소를 찾기 위한 매우 효율적이고 강력한 방법입니다. 이를 통해 복잡한 방향 그래프에서 중요한 연결 구조를 쉽게 파악할 수 있습니다. 본 글에서는 타잔 알고리즘의 동작 원리와 구현 방법을 자세히 살펴보았습니다. 다양한 그래프 문제에서 이 알고리즘을 적용해보면서 그 유용성을 직접 체험해보시길 추천드립니다.