그래프(Graph) 정리
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 서로 연결된 객체들의 관계를 나타내는 데 활용한다.
[알고리즘] 그래프(Graph) 정리
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 서로 연결된 객체들의 관계를 나타내는 데 활용한다. 예를 들어 도시와 도로, 사람과 친구 관계, 웹페이지와 하이퍼링크 등의 사례에서 그래프 구조가 적용되는 모습을 볼 수 있다.
1. 그래프의 구성 요소
그래프는 정점(Vertex)과 간선(Edge)으로 구성된다. 정점은 도시, 사람, 웹페이지와 같은 개체를 의미하며, 간선은 그 개체들을 잇는 ‘연결’ 혹은 ‘관계’를 의미한다. 방향성이 있는 유향 그래프(Directed Graph)와 방향성이 없는 무향 그래프(Undirected Graph)가 존재하며, 각 간선에 비용(거리, 시간 등) 정보를 부여한 가중치 그래프(Weighted Graph)도 자주 쓰인다.
2. 그래프 표현 방식
그래프를 프로그래밍 상에서 표현하는 대표적인 방법은 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 있다.
인접 행렬(Adjacency Matrix)
NxN 크기의 2차원 배열에 정보를 저장한다. 두 정점의 연결 여부를 빠르게 확인할 수 있지만, 간선이 적을 때는 공간이 낭비될 수 있다.인접 리스트(Adjacency List)
각 정점이 연결된 이웃 노드들의 목록을 저장한다. 필요한 간선 정보만 담으므로, 상대적으로 공간 효율이 높지만, 두 정점이 연결되어 있는지 확인할 때 리스트를 탐색해야 한다.
3. 깊이 우선 탐색(DFS, Depth-First Search)
가능한 한 깊숙이 파고들면서 방문하지 않은 노드를 찾는 방식을 취한다. 재귀(Recursive)나 스택(Stack)으로 구현하는 것이 일반적이다.
3.1 DFS 코드 예시 (재귀)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dfs(graph, start, visited=None):
"""
graph : 그래프 인접 리스트(딕셔너리)
start : 탐색을 시작할 정점
visited: 이미 방문한 정점을 저장할 집합(중복 방지)
"""
if visited is None: # 방문 집합이 전달되지 않았다면
visited = set() # 방문 집합을 빈 집합으로 초기화
visited.add(start) # 현재 정점을 '방문 처리'함
for neighbor in graph[start]: # 현재 정점의 이웃 정점들을 순회
if neighbor not in visited: # 아직 방문하지 않은 이웃이라면
dfs(graph, neighbor, visited) # 재귀 호출을 통해 깊이 탐색
return visited # 모든 이웃을 탐색한 뒤, 방문한 정점들을 반환
위 코드에서는 visited가 방문한 정점을 중복 없이 기록한다. 함수가 재귀적으로 호출되면서 계속해서 깊이 들어가게 되고, 방문을 마친 뒤에는 이전 단계로 되돌아가 나머지 이웃 정점을 탐색한다.
4. 너비 우선 탐색(BFS, Breadth-First Search)
시작 정점에서 가까운 노드부터 방문해 나가는 방식으로, 큐(Queue)를 사용한다. 첫 정점 주변의 모든 노드를 우선 탐색한 뒤, 다시 그 다음 단계로 넘어가며 진행한다.
4.1 BFS 코드 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import deque
def bfs(graph, start):
"""
graph: 그래프 인접 리스트(딕셔너리)
start: 탐색을 시작할 정점
"""
visited = set() # 방문한 정점을 저장할 집합
queue = deque([start]) # 양방향 큐(deque)에 시작 정점을 넣어 초기화
while queue: # 큐에 노드가 남아있는 동안 반복
node = queue.popleft() # 큐의 왼쪽(앞쪽)에서 노드를 하나 꺼냄
if node not in visited: # 아직 방문하지 않은 노드라면
visited.add(node) # 방문 처리
for neighbor in graph[node]: # 이 노드에 연결된 모든 이웃에 대하여
if neighbor not in visited:
queue.append(neighbor) # 방문 예정 노드를 큐의 오른쪽(뒤쪽)에 추가
return visited # 방문한 모든 노드를 담은 집합을 반환
위 구현에서는 큐에 들어간 노드를 순서대로 꺼내 방문하기 때문에, 탐색되는 순서가 시작 정점에서 ‘가까운 순서’로 진행된다.
5. 그래프 알고리즘 및 활용 사례
- 최단 경로 알고리즘
다익스트라(Dijkstra) 알고리즘이나 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall) 등은 특정 정점에서 다른 정점까지 이동 비용이 최소가 되도록 경로를 찾는다. - 최소 신장 트리(MST)
그래프 내 모든 정점을 연결하는 간선들의 집합 중, 비용의 합이 최소가 되도록 하는 구조를 말한다. 크루스컬(Kruskal), 프림(Prim) 알고리즘이 대표적이다. - 위상 정렬(Topological Sort)
순환이 없는 유향 그래프(DAG)에서, 선후관계를 만족시키도록 모든 정점을 나열하는 정렬이다. 작업 스케줄링, 강의 수강 순서 배치 등 순서가 중요한 문제에 활용된다.
6. 정리하며
그래프는 정점과 간선을 통해 다양한 관계를 표현하는 자료구조이며, DFS와 BFS는 이러한 그래프를 효율적으로 탐색하는 대표적인 알고리즘이다. 현실 세계에서는 지도/내비게이션, 소셜 네트워크, 웹, 통신/네트워크 등 다양한 분야에서 적용 사례를 찾을 수 있다. 각 문제 상황에 맞춰 적절한 알고리즘을 선택한다면, 복잡한 연결 관계도 효과적으로 모델링하고 해결하는 데 많은 도움이 된다.
팁
- 실제 프로젝트나 문제 해결 시에는, 그래프의 간선 밀도(Edge Density)를 고려하여 인접 행렬 혹은 인접 리스트 중 하나를 선택하면 좋다.
- DFS와 BFS 모두 그래프 탐색에 중요한 방법이므로, 자료구조나 알고리즘 학습을 시작할 때 반드시 익혀두면 여러 문제를 해결할 때 응용하기 편리하다.