파이썬으로 해보는 그래프 탐색 알고리즘 실전 강의

Python에서 그래프 탐색 알고리즘 실습해보기

그래프는 컴퓨터 과학에서 정보를 표현하는 중요한 구조 중 하나입니다. 다양한 네트워크, 소셜 미디어, 도로 및 통신 네트워크와 같은 시스템을 모델링하기 위해 그래프가 사용됩니다. 이 글에서는 그래프 탐색 알고리즘을 Python을 이용하여 실습하는 방법을 소개하겠습니다. 초보자도 이해할 수 있도록 간단히 설명할 것입니다.

그래프란 무엇인가?

그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조입니다. 정점은 객체를 나타내고, 간선은 정점 간의 관계를 나타냅니다. 그래프의 기본적인 특성은 다음과 같습니다.

• 정점(Vertex): 그래프에서 객체를 나타내는 점.
• 간선(Edge): 두 정점을 연결하는 선.
• 유향 그래프: 간선의 방향성이 있는 그래프.
• 무향 그래프: 간선의 방향성이 없는 그래프.
• 가중치 그래프: 간선에 가중치가 부여된 그래프.

그래프 탐색 알고리즘의 종류

그래프 탐색 알고리즘은 그래프의 정점과 간선을 순회하고 탐색하는 방법입니다. 대표적인 알고리즘에는 다음과 같은 것들이 있습니다.

• 깊이 우선 탐색(DFS): 하나의 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방법입니다.
• 너비 우선 탐색(BFS): 시작 정점에서 가까운 정점을 먼저 탐색하는 방법입니다.

깊이 우선 탐색(DFS)

깊이 우선 탐색은 스택 구조를 이용하여 그래프를 탐색하는 방법입니다. 이 알고리즘은 선택한 경로를 가능한 한 끝까지 내려간 후, 더 이상 갈 곳이 없을 때 돌아와서 다른 경로를 탐색합니다.

너비 우선 탐색(BFS)

너비 우선 탐색은 큐 구조를 이용하여 그래프를 탐색하는 방법입니다. 시작 정점에서 인접한 정점을 먼저 방문한 후, 그 정점의 인접 정점을 탐색합니다. 이 과정은 탐색할 정점이 없을 때까지 계속됩니다.

Python에서 그래프 구현하기

Python에서 그래프를 구현하기 위해 인접 리스트(Adjacency List) 방식을 사용할 것입니다. 인접 리스트는 각 정점에 대해 인접한 정점의 리스트를 유지하는 방법입니다. 다음은 그래프를 구현하는 코드 예제입니다.

class Graph:
    def init(self):
        self.graph = {}
    
    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)
    
    def print_graph(self):
        for vertex in self.graph:
            print(f"{vertex}: {self.graph[vertex]}")

위 코드에서는 Graph 클래스를 정의하고, addedge 메서드를 통해 간선을 추가하며, printgraph 메서드를 통하여 그래프를 출력합니다.

깊이 우선 탐색(DFS) 구현하기

이제 깊이 우선 탐색 알고리즘을 Python에서 구현해 보겠습니다. DFS는 재귀적으로 구현할 수 있습니다. 다음은 DFS를 구현한 코드 예제입니다.

def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    print(vertex)
    
    for neighbor in graph.get(vertex, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

이 코드는 주어진 정점에서 시작하여 모든 연결된 정점을 방문합니다. 방문한 정점은 visited 집합에 추가되어 중복 방문을 방지합니다.

너비 우선 탐색(BFS) 구현하기

이제 너비 우선 탐색 알고리즘을 Python에서 구현해 보겠습니다. BFS는 큐를 이용하여 구현합니다. 다음은 BFS를 구현한 코드 예제입니다.

from collections import deque

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(neighbor for neighbor in graph.get(vertex, []) if neighbor not in visited)

위 코드는 시작 정점에서 탐색을 시작하여 인접한 정점을 방문하면서 큐를 활용해 탐색합니다.

실습 예제: 그래프 탐색 종합하기

이제 실제로 그래프를 만들고, 깊이 우선 탐색과 너비 우선 탐색을 적용해 보겠습니다. 다음은 전체 예제 코드입니다.

그래프 생성

graph = Graph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(2, 5)
graph.add_edge(3, 6)

그래프 출력

graph.print_graph()

DFS 탐색

print("DFS 탐색 결과:")
dfs(graph.graph, 1)

BFS 탐색

print("BFS 탐색 결과:")
bfs(graph.graph, 1)

결론

이 글에서는 Python에서 그래프 탐색 알고리즘을 실습해 보았습니다. 깊이 우선 탐색과 너비 우선 탐색의 기본 개념과 실제 코딩 예제를 통해 이론과 실습을 병행하였습니다. graph 구조를 사용하여 기본적인 그래프 탐색 알고리즘을 구현하고 이를 통해 다양한 문제를 해결할 수 있는 기초를 다질 수 있었습니다.

앞으로 보다 복잡한 그래프 문제를 해결할 때, 이번 실습이 도움이 되기를 바랍니다. 다양한 자료구조와 알고리즘에 대한 이해가 깊어질수록 문제 해결 능력도 향상될 것입니다.