Colin's Blog
[python] 그래프 알고리즘

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 많은 문제들을 그래프로 모델링할 수 있고, 그래프 알고리즘을 사용하여 이러한 문제를 해결할 수 있습니다.

그래프 표현 방법

그래프는 다양한 방식으로 표현할 수 있습니다. 가장 일반적인 방법은 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)입니다.

인접 행렬(Adjacency Matrix)

인접 행렬은 2차원 배열로 그래프를 표현하는 방법입니다. 배열의 크기는 n x n이며, graph[i][j]가 1이면 정점 i와 j가 연결되어 있는 것을 의미하고, 0이면 연결되어 있지 않음을 의미합니다. 이 방법은 그래프의 크기가 작거나 간선의 수가 많을 때 효율적입니다.

graph = [[0]*n for _ in range(n)]

인접 리스트(Adjacency List)

인접 리스트는 리스트의 리스트로 그래프를 표현하는 방법입니다. graph[i]에는 정점 i와 연결된 정점들이 리스트로 저장되어 있습니다. 이 방법은 그래프의 크기가 크거나 간선의 수가 적을 때 효율적입니다.

graph = [[] for _ in range(n)]

그래프 알고리즘

깊이 우선 탐색은 그래프를 탐색하면서 각 정점을 방문하는 알고리즘입니다. 스택(Stack)을 사용하여 구현할 수 있습니다.

visited = [False] * n

def dfs(v):
    visited[v] = True
    print(v, end=" ")

    for i in graph[v]:
        if not visited[i]:
            dfs(i)

너비 우선 탐색은 그래프를 탐색하면서 각 정점을 방문하는 알고리즘입니다. 큐(Queue)를 사용하여 구현할 수 있습니다.

visited = [False] * n

def bfs(v):
    queue = [v]
    visited[v] = True

    while queue:
        current = queue.pop(0)
        print(current, end=" ")

        for i in graph[current]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

3. 최단 경로 알고리즘

최단 경로 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 대표적으로 다익스트라(Dijkstra) 알고리즘과 벨만-포드(Bellman-Ford) 알고리즘이 있습니다.

import heapq
import sys

def dijkstra(start):
    distance = [sys.maxsize] * n
    distance[start] = 0

    heap = []
    heapq.heappush(heap, (0, start))

    while heap:
        dist, current = heapq.heappop(heap)

        if dist > distance[current]:
            continue

        for node, cost in graph[current]:
            new_cost = dist + cost
            
            if new_cost < distance[node]:
                distance[node] = new_cost
                heapq.heappush(heap, (new_cost, node))

    return distance

결론

그래프 알고리즘은 다양한 문제를 해결하기 위한 중요한 자료구조입니다. 깊이 우선 탐색, 너비 우선 탐색, 최단 경로 알고리즘 등을 활용하여 다양한 그래프 문제를 효과적으로 해결할 수 있습니다.

참고 자료:

© 2018 Colin. All rights reserved.