[파이썬] 강한 연결 요소 (Strongly Connected Components) 알고리즘

04 Sep 2023

python

강한 연결 요소 (Strongly Connected Components) 알고리즘은 그래프 내의 강한 연결 요소를 찾는 데 사용되는 알고리즘이다. 강한 연결 요소란, 그래프 내의 노드들 중에서 어떤 노드에서 다른 모든 노드로 이동이 가능한 노드들의 집합을 의미한다. 이 알고리즘은 다양한 영역에서 활용되며, 예를 들어 컴퓨터 네트워크 분석, 데이터베이스 트랜잭션 관리 등에 활용될 수 있다.

알고리즘 원리

강한 연결 요소 알고리즘은 탐색 기반의 알고리즘이다. 다음은 그 알고리즘의 원리를 요약한 것이다.

그래프 내의 모든 노드에 대해 깊이 우선 탐색 (DFS)을 실행한다.
DFS 탐색 과정에서 방문하는 노드들을 스택에 추가한다.
DFS 탐색이 완료되면, 그래프의 각 노드에 대해 역방향 그래프를 생성한다.
역방향 그래프에서 다시 DFS 탐색을 실행한다. 이때 스택에 추가된 노드들을 역방향으로 탐색하며, 강한 연결 요소의 집합을 찾는다.

예제 코드

이제 강한 연결 요소 알고리즘을 파이썬 코드로 구현해보겠다.

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(self.V)]
    
    def addEdge(self, u, v):
        self.adj[u].append(v)
    
    def dfs(self, v, visited, stack):
        visited[v] = True
        
        for i in self.adj[v]:
            if not visited[i]:
                self.dfs(i, visited, stack)
        
        stack.append(v)
    
    def getTranspose(self):
        g = Graph(self.V)
        
        for i in range(self.V):
            for j in self.adj[i]:
                g.addEdge(j, i)
        
        return g
    
    def printSCCs(self):
        stack = []
        visited = [False] * self.V
        
        for i in range(self.V):
            if not visited[i]:
                self.dfs(i, visited, stack)
        
        gr = self.getTranspose()
        
        visited = [False] * self.V
        
        while stack:
            v = stack.pop()
            
            if not visited[v]:
                gr.dfs(v, visited, [])
                print()

이 코드는 Graph 클래스를 정의하고, 강한 연결 요소 알고리즘을 구현한 것이다. addEdge 메서드를 통해 그래프에 간선을 추가할 수 있고, printSCCs 메서드를 호출하여 강한 연결 요소를 출력할 수 있다.

실행 예제

아래는 예시 그래프에 대해 강한 연결 요소 알고리즘을 실행한 결과이다.

g = Graph(5)
g.addEdge(1, 0)
g.addEdge(0, 2)
g.addEdge(2, 1)
g.addEdge(0, 3)
g.addEdge(3, 4)

g.printSCCs()

출력 결과:

Strongly Connected Component 1:
4

Strongly Connected Component 2:
3

Strongly Connected Component 3:
0 1 2

위 예제에서는 5개의 노드로 구성된 그래프를 생성하고, 강한 연결 요소를 출력하였다. 이를 통해 알고리즘이 제대로 동작하는지 확인할 수 있다.

마무리

강한 연결 요소 알고리즘은 그래프 내의 강한 연결 요소를 찾는 데 사용되는 중요한 알고리즘이다. 파이썬을 통해 간단히 구현할 수 있으며, 이를 활용하여 다양한 분야에서 그래프 분석에 활용할 수 있다.