[415] 타잔의 SCC(강한 연결 요소) 알고리즘(파이썬 코드)

1. 강한 연결 요소 개념

이번 글에서는 파이썬으로 타잔의 SCC 알고리즘을 구현한 코드를 살펴보겠습니다.

강한 연결 요소에 대해 알고 싶으시다면 지난 글을 참고하세요.

https://kimwooil.tistory.com/380

[380] 강한 연결 요소(SCC)와 타잔의 SCC 알고리즘(Tarjan's SCC algorithm)

2. 타잔의 SCC 알고리즘 파이썬 코드

위 이미지와 같이 그래프의 강한 연결 요소를 찾아보겠습니다.

 

가. 그래프 초기화

위 이미지는 정점 8개와 간선 14개로 이루어져 있습니다.

파이썬으로 그래프를 구현하는 방법은 여러가지가 있습니다.

그 중 딕셔너리로 나타내어 보겠습니다.

파이썬 코드로 나타내면 다음과 같습니다.

graph = {
    1: [2],
    2: [3],
    3: [1],
    4: [2, 3, 5],
    5: [4, 6],
    6: [3, 7],
    7: [6],
    8: [5, 7, 8]
}

나. 변수 정의

index = 0  # 탐색 정점마다 고유한 id값을 부여하기 위해 사용되는 변수
node_id = [0] * (len(graph) + 1)  # 정점을 탐색하면서 고유한 id값을 저장하는 리스트, 탐색 여부도 판단
finished = [0] * (len(graph) + 1)  # 정점의 scc 확인을 마쳤는지 확인하는 리스트
stack = []  # 탐색 정점을 담아 관리할 stack
res = []  # 탐색을 마친 scc를 기록하는 결과 출력용 리스트

탐색을 마쳤는지, scc 확인을 마쳤는지를 각각 별도의 변수(node_id와 finished)를 정의하여 따로 관리합니다.

다. 함수 정의

def scc(u):
    global index
    index += 1  # 함수가 실행될 때마다 1씩 증가하며 탐색 시 정점마다 고유한 id를 부여
    lowlink = node_id[u] = index  # lowlink 값 초기화, 정점의 고유한 id 기록
    stack.append(u)  # stack에 탐색하는 정점을 차례대로 쌓습니다.

    for v in graph[u]: # 정점 u에 연결된 정점 v들을 탐색
        if node_id[v] == 0:  # 탐색되지 않은 정점일 경우
            lowlink = min(lowlink, scc(v))
        elif finished[v] == 0:  # 탐색은 되었으나 scc 확인이 안 된 정점일 경우(사이클인 경우)
            lowlink = min(lowlink, node_id[v])
    
    if lowlink == node_id[u]:  # lowlink의 변화가 없는 경우(사이클을 돌고 다시 자신으로 돌아온 경우)
        components = []  # 강한 연결 요소를 저장할 임시 리스트
        while stack:  # 자신이 나올 때 까지 하나씩 꺼내 강한 연결 요소로 등록
            v = stack.pop()
            components.append(v)
            finished[v] = 1  # 강한 연결 요소 확인 완료 기록
            if u == v:  # stack에서 하나씩 꺼내다 자신이 나오면 종료
                break
        res.append(components)  # 강한 연결 요소를 결과에 기록
        
    return lowlink  # 재귀적으로 dfs를 구현하기 위해 lowlink 값을 반환

라. 실행 코드

for u in range(1, len(graph)+1):  # 1번 정점부터 마지막 정점까지 scc 함수를 이용해 dfs를 실행
    if finished[u] == 0:
        scc(u)

print(res)  # 결과를 출력

마. 출력 결과

[[3, 2, 1], [7, 6], [5, 4], [8]]

바. 전체 코드

# 그래프 초기화
graph = {
    1: [2],
    2: [3],
    3: [1],
    4: [2, 3, 5],
    5: [4, 6],
    6: [3, 7],
    7: [6],
    8: [5, 7, 8]
}

# 변수 정의
index = 0
node_id = [0] * (len(graph) + 1)
finished = [0] * (len(graph) + 1)
stack = []
res = []

# 함수 정의
def scc(u):
    global index
    index += 1
    lowlink = node_id[u] = index
    stack.append(u)

    for v in graph[u]:
        if node_id[v] == 0:
            lowlink = min(lowlink, scc(v))
        elif finished[v] == 0:
            lowlink = min(lowlink, node_id[v])
    
    if lowlink == node_id[u]:
        components = []
        while stack:
            v = stack.pop()
            components.append(v)
            finished[v] = 1
            if u == v:
                break
        res.append(components)
        
    return lowlink

# 함수 실행(DFS 수행)
for u in range(1, len(graph)+1):
    if finished[u] == 0:
        scc(u)

# 출력
print(res)

# 출력 결과
# [[3, 2, 1], [7, 6], [5, 4], [8]]