그래프(Graph): 네트워크와 관계 데이터를 표현하는 강력한 자료구조
🔹 그래프란?
1. 그래프(Graph)의 정의
그래프(Graph)는 노드(Node, 정점)와 엣지(Edge, 간선)로 구성된 비선형 데이터 구조로, 객체 간의 관계를 표현하는 데 사용됩니다. 그래프는 소셜 네트워크, 지도 경로 탐색, 웹 크롤링, 네트워크 라우팅 등 다양한 분야에서 필수적인 자료구조입니다.
✅ 그래프의 주요 특징:
- 정점(Vertex, Node): 데이터를 저장하는 요소
- 간선(Edge): 노드 간의 관계를 나타내는 연결선
- 방향 그래프(Directed Graph, 유향 그래프)와 무방향 그래프(Undirected Graph, 무향 그래프)로 구분
- 가중 그래프(Weighted Graph)와 비가중 그래프(Unweighted Graph)로 구분
📌 그래프는 네트워크 구조를 모델링하는 데 최적화된 자료구조입니다.
🔹 그래프의 유형
1. 무방향 그래프(Undirected Graph)
✅ 노드 간의 간선이 방향성을 가지지 않는 그래프
✔️ 예제:
A ---- B
| |
C ---- D📌 소셜 네트워크에서 친구 관계를 나타내는 데 활용됩니다.
2. 방향 그래프(Directed Graph, 유향 그래프)
✅ 간선이 방향성을 가지며, 한쪽으로만 이동 가능한 그래프
✔️ 예제:
A → B → C
↑ ↓
D ← E📌 웹페이지 링크, 네트워크 패킷 흐름 등을 모델링하는 데 사용됩니다.
3. 가중 그래프(Weighted Graph)
✅ 각 간선이 특정 가중치(비용)를 가지는 그래프
✔️ 예제:
A --(4)-- B
| |
(2) (3)
| |
C --(1)-- D📌 GPS 내비게이션에서 최단 경로를 계산하는 데 사용됩니다.
4. 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)
✅ 그래프를 표현하는 방법으로, 효율성에 따라 선택됨
✔️ 인접 행렬:
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0📌 O(1)으로 간선 확인 가능하지만, 메모리 사용량이 많음
✔️ 인접 리스트 (Python 표현):
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}📌 메모리 사용이 적고, 연결된 노드만 저장하여 효율적
🔹 그래프 탐색 알고리즘
1. 깊이 우선 탐색(DFS, Depth-First Search) - O(V+E)
✅ 한 경로를 끝까지 탐색한 후, 다시 돌아가 다른 경로를 탐색하는 방식
✔️ DFS 예제 (Python):
def dfs(graph, node, visited):
if node not in visited:
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
visited = set()
dfs(graph, 'A', visited) # 출력: A B D E F C📌 DFS는 백트래킹, 미로 탐색, 순열 생성 등에 활용됩니다.
2. 너비 우선 탐색(BFS, Breadth-First Search) - O(V+E)
✅ 현재 노드의 모든 인접 노드를 먼저 방문한 후, 다음 깊이로 이동하는 방식
✔️ BFS 예제 (Python):
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
print(node, end=' ')
queue.extend(graph[node])
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A') # 출력: A B C D E F📌 BFS는 최단 경로 탐색, 네트워크 탐색, 웹 크롤링 등에 활용됩니다.
🔹 최단 경로 알고리즘
1. 다익스트라 알고리즘(Dijkstra’s Algorithm) - O((V+E) log V)
✅ 가중 그래프에서 출발점에서 모든 노드까지의 최단 경로를 찾는 알고리즘
✔️ 다익스트라 알고리즘 예제 (Python):
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].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, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))📌 네비게이션 시스템, 네트워크 경로 탐색에 사용됩니다.
📌 결론
✅ 그래프(Graph)는 네트워크, 지도, 관계 데이터를 표현하는 핵심 데이터 구조입니다.
✅ DFS, BFS, 다익스트라 알고리즘 등을 활용하여 그래프 탐색 및 최단 경로를 찾을 수 있습니다.
✅ 그래프는 소셜 네트워크 분석, 검색 엔진, 인공지능 등 다양한 분야에서 활용됩니다.