로고

그래프 알고리즘 마스터하기: DFS, BFS, 다익스트라, 크루스칼

작성일 :

그래프 알고리즘 마스터하기: DFS, BFS, 다익스트라, 크루스칼

그래프 알고리즘은 다양한 문제를 효율적으로 해결하기 위해 필수적으로 알아야 할 개념입니다. 네트워크 구조를 파악하거나, 최단 경로를 찾거나, 최적의 연결을 찾는 등의 문제에 활용됩니다. 이 글에서는 그래프 알고리즘의 기본 개념과 함께 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 다익스트라 알고리즘, 그리고 크루스칼 알고리즘을 자세히 설명합니다.

그래프의 기본 개념

그래프는 정점(vertex)과 정점 사이를 연결하는 간선(edge)으로 구성된 데이터 구조입니다. 그래프는 방향 그래프와 무방향 그래프로 나뉘며, 가중치 그래프와 무가중치 그래프도 있습니다. 그래프를 표현하는 방법으로는 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)가 있습니다.

인접 행렬과 인접 리스트

  1. 인접 행렬: 정점 i와 j가 연결되어 있으면, 행렬의 i행 j열 값을 1(또는 가중치 값)로 설정합니다. 그렇지 않으면 0으로 설정합니다.
  2. 인접 리스트: 각 정점의 리스트가 그 정점과 인접한 정점을 포함합니다. 가중치가 있을 경우, 리스트 노드에 가중치도 포함됩니다.

깊이 우선 탐색 (DFS)

깊이 우선 탐색(DFS, Depth First Search)은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 한 방향으로 끝까지 탐색하다가 더 이상 진출할 길이 없으면 마지막으로 왔던 갈림길로 돌아와서 다시 다른 방향으로 탐색을 계속하는 방식입니다.

DFS의 동작 방식

  1. 현재 정점을 방문하고, 방문 사실을 기록합니다.
  2. 현재 정점에 인접한 정점 중 방문하지 않은 정점으로 이동합니다.
  3. 더 이상 방문할 수 있는 정점이 없으면, 이전 정점으로 돌아갑니다.

DFS 구현 예제 (파이썬)

python
# 그래프를 인접 리스트 형태로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = set()

def dfs(vertex):
    if vertex not in visited:
        print(vertex)
        visited.add(vertex)
        for neighbor in graph[vertex]:
            dfs(neighbor)

# DFS 호출
dfs('A')

너비 우선 탐색 (BFS)

너비 우선 탐색(BFS, Breadth First Search)은 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 출발하여 인접한 정점들을 먼저 방문한 후, 그 다음 인접한 정점들을 방문하는 방식입니다.

BFS의 동작 방식

  1. 시작 정점을 방문하고, 큐(queue)에 삽입합니다.
  2. 큐에서 정점을 꺼내 해당 정점에 인접한 방문하지 않은 정점을 모두 큐에 삽입합니다.
  3. 큐가 빌 때까지 2번 과정을 반복합니다.

BFS 구현 예제 (파이썬)

python
from collections import deque

# 그래프를 인접 리스트 형태로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = set()
queue = deque(['A'])

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

다익스트라 알고리즘

다익스트라 알고리즘(Dijkstra's algorithm)은 가중치가 있는 그래프에서 특정 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 음의 가중치를 가지는 경우에는 사용할 수 없습니다.

다익스트라 알고리즘의 동작 방식

  1. 시작 정점을 설정하고, 해당 정점의 거리를 0으로 설정합니다.
  2. 나머지 정점의 거리는 무한대(∞)로 설정합니다.
  3. 현재 정점에서 인접한 정점의 거리를 갱신합니다.
  4. 모든 정점을 방문할 때까지, 가장 가까운(최단 거리) 정점을 선택하고 같은 과정을 반복합니다.

다익스트라 알고리즘 구현 예제 (파이썬)

python
import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# 그래프를 인접 리스트 형태로 표현
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 5},
    'C': {'A': 4, 'F': 3},
    'D': {'B': 2},
    'E': {'B': 5, 'F': 1},
    'F': {'C': 3, 'E': 1}
}

# 다익스트라 알고리즘 호출
print(dijkstra(graph, 'A'))

크루스칼 알고리즘

크루스칼 알고리즘(Kruskal's algorithm)은 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘입니다. 가중치가 있는 연결된 무방향 그래프에서 모든 정점을 연결하는 부분 그래프 중 가중치의 합이 최소가 되는 트리를 찾습니다.

크루스칼 알고리즘의 동작 방식

  1. 모든 간선을 가중치의 오름차순으로 정렬합니다.
  2. 가장 작은 가중치의 간선부터 추가합니다. 이때, 사이클이 생기지 않도록 합니다.
  3. 모든 정점이 연결될 때까지 2번 과정을 반복합니다.

크루스칼 알고리즘 구현 예제 (파이썬)

python
class DisjointSet:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            self.parent[item] = self.find(self.parent[item])
            return self.parent[item]

    def union(self, set1, set2):
        root1 = self.find(set1)
        root2 = self.find(set2)

        if root1 != root2:
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            else:
                self.parent[root1] = root2
                if self.rank[root1] == self.rank[root2]:
                    self.rank[root2] += 1


def kruskal(graph):
    edges = sorted(graph['edges'], key=lambda edge: edge[2])
    ds = DisjointSet(graph['vertices'])
    mst = []

    for edge in edges:
        u, v, weight = edge
        if ds.find(u) != ds.find(v):
            mst.append(edge)
            ds.union(u, v)

    return mst

# 그래프를 간선 리스트 형태로 표현
graph = {
    'vertices': ['A', 'B', 'C', 'D', 'E', 'F'],
    'edges': [
        ('A', 'B', 1),
        ('A', 'C', 4),
        ('B', 'D', 2),
        ('B', 'E', 5),
        ('C', 'F', 3),
        ('E', 'F', 1)
    ]
}

# 크루스칼 알고리즘 호출
print(kruskal(graph))

결론

그래프 알고리즘은 다양한 문제 해결에 효율적인 도구를 제공합니다. DFS와 BFS는 그래프 탐색에, 다익스트라 알고리즘은 최단 경로 문제에, 크루스칼 알고리즘은 최소 신장 트리 문제에 각각 효과적입니다. 이러한 알고리즘들을 이해하고 구현해 봄으로써 그래프 이론을 더 깊이 이해할 수 있습니다.