[파이썬] 그래프 순회의 응용 (연결 요소, 사이클 찾기 등)

04 Sep 2023

python

그래프는 다양한 문제 해결에 사용되는 중요한 자료 구조입니다. 그래프의 순회 알고리즘을 이용하여 연결 요소를 찾거나 사이클을 찾는 등의 문제를 해결할 수 있습니다. 이번 포스트에서는 이러한 응용에 대해 알아보고, 파이썬을 이용하여 구현하는 방법을 살펴보겠습니다.

연결 요소 (Connected Components)

연결 요소는 그래프에서 모든 정점이 연결되어 있는 부분 그래프를 의미합니다. 즉, 각 연결 요소는 독립된 그래프로 이루어져 있으며, 서로 다른 연결 요소 간에는 경로가 존재하지 않습니다.

연결 요소를 찾는 가장 간단한 방법은 깊이 우선 탐색 (Depth-First Search, DFS) 알고리즘을 이용하는 것입니다. DFS는 하나의 정점에서부터 시작하여 이동 가능한 모든 정점을 순회하고, 이동 가능한 정점이 없을 때까지 계속하여 탐색합니다. 이를 이용하여 연결 요소를 찾는 코드는 다음과 같습니다.

def dfs(graph, start, visited):
    visited[start] = True
    print(start, end=" ")  # 방문한 정점 출력
    
    for neighbor in graph[start]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

def find_connected_components(graph):
    num_vertices = len(graph)
    visited = [False] * num_vertices
    
    for v in range(num_vertices):
        if not visited[v]:
            dfs(graph, v, visited)
            print()  # 연결 요소 간 구분을 위한 개행

# 그래프 정의 (인접 리스트)
graph = [
    [1, 2],
    [0, 2],
    [0, 1],
    [3],
    [4],
    [5],
    [6, 7],
    [6]
]

# 연결 요소 찾기
find_connected_components(graph)

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

각 줄은 한 연결 요소를 의미하며, 각 연결 요소 내에서는 순회한 정점들이 출력됩니다.

사이클 찾기 (Cycle Detection)

사이클은 그래프 내에서 반복적인 경로를 의미합니다. 사이클을 찾는 문제는 주어진 그래프에서 사이클이 존재하는지 여부를 판별하는 것입니다. 이 역시 DFS 알고리즘을 응용하여 사이클을 찾을 수 있습니다.

사이클을 찾기 위해서는 방문한 정점을 표시하는 배열에 추가로 현재 경로에 포함된 정점을 따로 표시해야 합니다. 이를 이용하여 사이클을 찾는 코드는 다음과 같습니다.

def dfs_cycle(graph, start, visited, path):
    visited[start] = True
    path[start] = True  # 현재 경로에 포함된 정점 표시
    
    for neighbor in graph[start]:
        if path[neighbor]:
            return True  # 사이클 발견
        
        if not visited[neighbor]:
            if dfs_cycle(graph, neighbor, visited, path):
                return True
    
    path[start] = False  # 현재 경로에 포함된 정점 표시 해제
    return False

def has_cycle(graph):
    num_vertices = len(graph)
    visited = [False] * num_vertices
    path = [False] * num_vertices
    
    for v in range(num_vertices):
        if not visited[v]:
            if dfs_cycle(graph, v, visited, path):
                return True
    
    return False

# 그래프 정의 (인접 리스트)
graph = [
    [1, 2],
    [2],
    [3, 4],
    [0],
    []
]

# 사이클 여부 판별
print(has_cycle(graph))  # True

graph = [
    [1],
    [2],
    [3],
    [0]
]

print(has_cycle(graph))  # False

위 코드를 실행하면 첫 번째 그래프는 사이클이 존재하므로 True를, 두 번째 그래프는 사이클이 존재하지 않으므로 False를 출력합니다.

그래프 순회의 응용 중 연결 요소와 사이클을 찾는 방법들을 파이썬을 이용하여 구현해 보았습니다. 이러한 알고리즘은 실제로 그래프 기반의 문제를 해결하는 데에 많이 활용됩니다. 다음에는 그래프 순회의 더 다양한 응용에 대해 알아보도록 하겠습니다.