그래프 탐색은 그래프 내의 모든 정점을 방문하거나 원하는 정점을 찾는 알고리즘입니다. 이러한 알고리즘은 다양한 문제를 해결하는 데에 사용됩니다. 이번에는 파이썬의 NetworkX 라이브러리를 이용하여 그래프 탐색 알고리즘을 구현하는 방법을 알아보겠습니다.

1. NetworkX 설치하기

NetworkX는 파이썬에서 그래프를 다루기 위한 라이브러리입니다. 먼저, NetworkX를 설치해야 합니다. 아래의 명령어를 사용하여 설치할 수 있습니다.

pip install networkx

2. 그래프 생성하기

우선, 탐색을 수행할 그래프를 생성해야 합니다. NetworkX에서는 Graph 클래스를 사용하여 그래프를 생성할 수 있습니다. 다음은 간단한 그래프를 생성하는 예제 코드입니다.

import networkx as nx

# 그래프 생성
G = nx.Graph()

# 정점 추가
G.add_nodes_from([1, 2, 3, 4])

# 간선 추가
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1)])

# 그래프 정보 출력
print(nx.info(G))

위의 코드를 실행하면, 4개의 정점과 4개의 간선을 가진 그래프가 생성되고, 그래프의 정보가 출력됩니다.

3. 그래프 탐색 알고리즘 구현하기

NetworkX는 다양한 그래프 탐색 알고리즘을 제공합니다. 가장 일반적인 알고리즘인 DFS(Depth-First Search)와 BFS(Breadth-First Search)를 구현하는 방법을 알아보겠습니다.

3.1 DFS 구현하기

DFS는 깊이 우선 탐색으로, 한 정점에서 시작하여 가능한 한 깊숙히 탐색한 후, 필요하다면 되돌아가서 다른 경로를 탐색합니다.

아래는 DFS 알고리즘을 구현한 예제 코드입니다.

# DFS 알고리즘 구현
def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            stack.extend(set(graph[vertex]) - visited)

위의 코드에서 graph는 그래프 자료 구조를, start는 탐색을 시작할 정점을 나타냅니다. DFS 알고리즘은 재귀적인 방식으로 구현될 수도 있지만, 여기서는 스택을 이용한 반복적인 방식으로 구현했습니다.

3.2 BFS 구현하기

BFS는 너비 우선 탐색으로, 한 정점에서 시작하여 인접한 모든 정점을 방문한 후, 그 다음으로 인접한 정점들을 방문하는 방식입니다.

아래는 BFS 알고리즘을 구현한 예제 코드입니다.

from collections import deque

# BFS 알고리즘 구현
def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)

위의 코드에서 graph와 start는 DFS와 동일하게 그래프와 탐색을 시작할 정점을 나타냅니다. BFS 알고리즘은 큐를 이용하여 구현됩니다.

마무리

위의 방법을 사용하여 파이썬 NetworkX를 이용하여 그래프 탐색 알고리즘을 구현하는 방법을 알아보았습니다. NetworkX는 다양한 그래프 알고리즘을 제공하므로, 필요에 따라 해당 라이브러리를 적절히 활용하여 그래프 탐색 문제를 해결할 수 있습니다.

참고링크:

• NetworkX 공식 문서
• 파이썬 문서

#graph #networkx