그래프 자료구조 | 인접 리스트, 인접 행렬, 탐색 완벽 정리
이 글의 핵심
그래프 자료구조에 대한 실전 가이드입니다. 인접 리스트, 인접 행렬, 탐색 완벽 정리 등을 예제와 함께 상세히 설명합니다.
들어가며
”연결 관계를 표현하는 자료구조”
그래프는 노드(정점)와 간선으로 이루어진 자료구조입니다. 트리보다 일반적인 구조로, 사이클을 허용하며 네트워크, 지도, 소셜 관계 등 실생활의 복잡한 연결 관계를 표현할 수 있습니다.
이 글을 읽으면
- 그래프의 기본 용어와 종류를 이해합니다
- 인접 리스트와 인접 행렬의 차이를 구분합니다
- BFS와 DFS로 그래프를 탐색하는 코드를 작성합니다
- 실무에서 그래프를 활용하는 사례를 학습합니다
목차
1. 그래프 기본
용어 정리
1 --- 2
| |
3 --- 4
- 정점(Vertex/Node): 1, 2, 3, 4
- 간선(Edge): 1-2, 1-3, 2-4, 3-4
- 차수(Degree): 정점에 연결된 간선 수
- 1의 차수 = 2 (1-2, 1-3)
- 2의 차수 = 2 (1-2, 2-4)
- 경로(Path): 1 → 2 → 4
- 사이클(Cycle): 1 → 2 → 4 → 3 → 1그래프 종류
1) 방향 그래프 (Directed Graph)
1 → 2
↓ ↓
3 → 4
- 간선에 방향 있음
- A → B는 가능, B → A는 불가능
- 예: 웹 페이지 링크, 작업 의존성2) 무방향 그래프 (Undirected Graph)
1 - 2
| |
3 - 4
- 간선에 방향 없음
- A - B는 양방향 가능
- 예: 친구 관계, 도로망3) 가중치 그래프 (Weighted Graph)
5
1 --- 2
| 3 |
3 --- 4
2
- 간선에 가중치(비용) 있음
- 예: 거리, 시간, 비용4) 순환 그래프 vs 비순환 그래프
순환 (Cyclic):
1 → 2
↑ ↓
3 ← 4
비순환 (Acyclic):
1 → 2
↓ ↓
3 → 42. 그래프 표현
인접 리스트 (Adjacency List)
정의: 각 정점마다 연결된 이웃 정점들의 리스트를 저장
장점:
- 공간 효율: O(V + E)
- 희소 그래프에 적합
- 이웃 순회 빠름
단점:
- 간선 존재 확인 느림: O(V)
Python 구현
# 무방향 그래프
graph = {
1: [2, 3],
2: [1, 4],
3: [1, 4],
4: [2, 3]
}
# 방향 그래프
directed_graph = {
1: [2, 3],
2: [4],
3: [4],
4: []
}
# 가중치 그래프
weighted_graph = {
1: [(2, 5), (3, 3)], # (노드, 가중치)
2: [(1, 5), (4, 2)],
3: [(1, 3), (4, 2)],
4: [(2, 2), (3, 2)]
}
# 간선 리스트에서 인접 리스트 생성
def build_graph(n, edges, directed=False):
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
if not directed:
graph[b].append(a)
return graph
# 사용
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
graph = build_graph(4, edges)
print(graph)
# {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}C++ 구현
#include <vector>
#include <iostream>
using namespace std;
// 무방향 그래프
vector<vector<int>> buildGraph(int n, const vector<pair<int, int>>& edges) {
vector<vector<int>> graph(n);
for (const auto& [a, b] : edges) {
graph[a].push_back(b);
graph[b].push_back(a);
}
return graph;
}
// 가중치 그래프
vector<vector<pair<int, int>>> buildWeightedGraph(
int n,
const vector<tuple<int, int, int>>& edges
) {
vector<vector<pair<int, int>>> graph(n);
for (const auto& [a, b, weight] : edges) {
graph[a].push_back({b, weight});
graph[b].push_back({a, weight});
}
return graph;
}
int main() {
vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};
auto graph = buildGraph(4, edges);
for (int i = 0; i < graph.size(); ++i) {
cout << i << ": ";
for (int neighbor : graph[i]) {
cout << neighbor << " ";
}
cout << "\n";
}
return 0;
}인접 행렬 (Adjacency Matrix)
정의: V×V 2차원 배열에서 matrix[i][j]가 간선 존재 여부 또는 가중치
장점:
- 간선 확인 빠름: O(1)
- 구현 간단
단점:
- 공간 비효율: O(V²)
- 밀집 그래프에만 적합
Python 구현
# 무방향 그래프 (4개 정점)
graph = [
[0, 1, 1, 0], # 0번 정점
[1, 0, 0, 1], # 1번 정점
[1, 0, 0, 1], # 2번 정점
[0, 1, 1, 0] # 3번 정점
]
# 가중치 그래프 (0은 연결 없음)
weighted_graph = [
[0, 5, 3, 0],
[5, 0, 0, 2],
[3, 0, 0, 2],
[0, 2, 2, 0]
]
# 간선 확인
if graph[0][1] == 1:
print("0-1 연결됨")
# 간선 리스트에서 인접 행렬 생성
def build_matrix(n, edges, directed=False):
matrix = [[0] * n for _ in range(n)]
for a, b in edges:
matrix[a][b] = 1
if not directed:
matrix[b][a] = 1
return matrix
# 사용
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
matrix = build_matrix(4, edges)
print(matrix)
# [[0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0]]비교표
| 특징 | 인접 리스트 | 인접 행렬 |
|---|---|---|
| 공간 | O(V+E) | O(V²) |
| 간선 확인 | O(V) | O(1) |
| 전체 순회 | O(V+E) | O(V²) |
| 구현 | 복잡 | 간단 |
| 적합 | 희소 그래프 (E << V²) | 밀집 그래프 (E ≈ V²) |
| 예시 | 소셜 네트워크 | 완전 그래프 |
3. 그래프 탐색
BFS (너비 우선 탐색)
원리: 시작 정점에서 가까운 정점부터 방문
구현 (Python):
from collections import deque
def bfs(graph, start):
"""
BFS 탐색
- 큐 사용
- 최단 경로 보장 (무가중치)
"""
visited = set([start])
queue = deque([start])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# 테스트
graph = {
1: [2, 3],
2: [1, 4],
3: [1, 4],
4: [2, 3]
}
print(bfs(graph, 1)) # [1, 2, 3, 4]구현 (C++):
#include <vector>
#include <queue>
#include <unordered_set>
#include <iostream>
using namespace std;
vector<int> bfs(const vector<vector<int>>& graph, int start) {
unordered_set<int> visited;
queue<int> q;
vector<int> result;
visited.insert(start);
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
return result;
}
int main() {
vector<vector<int>> graph = {
{1, 2}, // 0번 정점
{0, 3}, // 1번 정점
{0, 3}, // 2번 정점
{1, 2} // 3번 정점
};
auto result = bfs(graph, 0);
for (int node : result) {
cout << node << " ";
}
// 출력: 0 1 2 3
return 0;
}시간 복잡도: O(V + E)
공간 복잡도: O(V)
DFS (깊이 우선 탐색)
원리: 한 경로를 끝까지 탐색 후 백트래킹
구현 (Python - 재귀):
def dfs_recursive(graph, node, visited, result):
"""
DFS 탐색 (재귀)
- 스택 사용 (암시적)
- 모든 경로 탐색
"""
visited.add(node)
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, result)
# 사용
graph = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]}
visited = set()
result = []
dfs_recursive(graph, 1, visited, result)
print(result) # [1, 2, 4, 3]구현 (Python - 반복):
def dfs_iterative(graph, start):
"""
DFS 탐색 (반복)
- 명시적 스택 사용
"""
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return result
# 테스트
print(dfs_iterative(graph, 1)) # [1, 2, 4, 3]구현 (C++):
#include <vector>
#include <stack>
#include <unordered_set>
#include <iostream>
using namespace std;
vector<int> dfs(const vector<vector<int>>& graph, int start) {
unordered_set<int> visited;
stack<int> st;
vector<int> result;
st.push(start);
while (!st.empty()) {
int node = st.top();
st.pop();
if (visited.find(node) == visited.end()) {
visited.insert(node);
result.push_back(node);
for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
if (visited.find(*it) == visited.end()) {
st.push(*it);
}
}
}
}
return result;
}
int main() {
vector<vector<int>> graph = {
{1, 2}, // 0번 정점
{0, 3}, // 1번 정점
{0, 3}, // 2번 정점
{1, 2} // 3번 정점
};
auto result = dfs(graph, 0);
for (int node : result) {
cout << node << " ";
}
// 출력: 0 1 3 2
return 0;
}시간 복잡도: O(V + E)
공간 복잡도: O(V)
4. 고급 활용
1) 연결 요소 개수 (Connected Components)
문제: 무방향 그래프에서 연결된 컴포넌트 개수 찾기
Python 구현
def count_components(n, edges):
"""
연결 요소 개수
- Union-Find 또는 DFS 사용
"""
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for i in range(n):
if i not in visited:
dfs(i)
count += 1
return count
# 테스트
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(count_components(n, edges)) # 2
# 컴포넌트 1: {0, 1, 2}
# 컴포넌트 2: {3, 4}2) 사이클 감지
방향 그래프:
def has_cycle_directed(graph):
"""
방향 그래프 사이클 감지
- 재귀 스택 추적
"""
visited = set()
rec_stack = set()
def dfs(node):
visited.add(node)
rec_stack.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor):
return True
elif neighbor in rec_stack:
return True
rec_stack.remove(node)
return False
for node in graph:
if node not in visited:
if dfs(node):
return True
return False
# 테스트
graph = {1: [2], 2: [3], 3: [1]} # 사이클: 1→2→3→1
print(has_cycle_directed(graph)) # True무방향 그래프:
def has_cycle_undirected(graph):
"""
무방향 그래프 사이클 감지
- 부모 노드 추적
"""
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
for node in graph:
if node not in visited:
if dfs(node, -1):
return True
return False
# 테스트
graph = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]}
print(has_cycle_undirected(graph)) # True (1-2-4-3-1)3) 위상 정렬 (Topological Sort)
문제: 방향 비순환 그래프(DAG)에서 선후 관계 정렬
Python 구현 (Kahn’s Algorithm)
from collections import deque, defaultdict
def topological_sort(n, edges):
"""
위상 정렬 (Kahn's Algorithm)
- 진입 차수 0인 노드부터 처리
"""
graph = defaultdict(list)
in_degree = [0] * n
for a, b in edges:
graph[a].append(b)
in_degree[b] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != n:
return []
return result
# 테스트 (과목 선수 조건)
n = 4
edges = [[1, 0], [2, 0], [3, 1], [3, 2]]
# 3 → 1 → 0
# ↘ 2 ↗
print(topological_sort(n, edges)) # [3, 1, 2, 0] 또는 [3, 2, 1, 0]시간 복잡도: O(V + E)
5. 실무 사례
사례 1: 소셜 네트워크 - 친구 추천
시나리오: 친구의 친구 중 아직 친구가 아닌 사람 추천
Python 구현
from collections import defaultdict
class SocialNetwork:
def __init__(self):
self.graph = defaultdict(set)
def add_friendship(self, user1, user2):
self.graph[user1].add(user2)
self.graph[user2].add(user1)
def recommend_friends(self, user, limit=5):
"""
친구의 친구 추천
- 2-hop 거리의 사용자
- 공통 친구 수로 정렬
"""
friends = self.graph[user]
candidates = defaultdict(int)
for friend in friends:
for friend_of_friend in self.graph[friend]:
if friend_of_friend != user and friend_of_friend not in friends:
candidates[friend_of_friend] += 1
sorted_candidates = sorted(
candidates.items(),
key=lambda x: x[1],
reverse=True
)
return [user_id for user_id, _ in sorted_candidates[:limit]]
# 사용
network = SocialNetwork()
network.add_friendship('Alice', 'Bob')
network.add_friendship('Bob', 'Charlie')
network.add_friendship('Bob', 'David')
network.add_friendship('Charlie', 'Eve')
print(network.recommend_friends('Alice'))
# ['Charlie', 'David'] (Bob을 통한 연결)사례 2: 작업 스케줄링 - 의존성 해결
시나리오: 빌드 시스템에서 작업 순서 결정
Python 구현
from collections import defaultdict, deque
class TaskScheduler:
def __init__(self):
self.graph = defaultdict(list)
self.in_degree = defaultdict(int)
def add_dependency(self, task, depends_on):
"""
task는 depends_on 이후에 실행
"""
self.graph[depends_on].append(task)
self.in_degree[task] += 1
if depends_on not in self.in_degree:
self.in_degree[depends_on] = 0
def get_execution_order(self):
"""
위상 정렬로 실행 순서 반환
"""
queue = deque([task for task, degree in self.in_degree.items() if degree == 0])
result = []
while queue:
task = queue.popleft()
result.append(task)
for dependent in self.graph[task]:
self.in_degree[dependent] -= 1
if self.in_degree[dependent] == 0:
queue.append(dependent)
if len(result) != len(self.in_degree):
raise ValueError("순환 의존성 감지!")
return result
# 사용
scheduler = TaskScheduler()
scheduler.add_dependency('compile', 'download')
scheduler.add_dependency('test', 'compile')
scheduler.add_dependency('deploy', 'test')
scheduler.add_dependency('compile', 'generate')
print(scheduler.get_execution_order())
# ['download', 'generate', 'compile', 'test', 'deploy']사례 3: 미로 탐색 - 최단 경로
시나리오: 2D 그리드에서 시작점에서 도착점까지 최단 경로
Python 구현
from collections import deque
def shortest_path_grid(grid, start, end):
"""
2D 그리드 최단 경로
- BFS 사용
- 0: 통행 가능, 1: 벽
"""
rows, cols = len(grid), len(grid[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
queue = deque([(start[0], start[1], 0)])
visited = {start}
while queue:
r, c, dist = queue.popleft()
if (r, c) == end:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
grid[nr][nc] == 0 and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
# 테스트
grid = [
[0, 0, 1, 0],
[0, 0, 0, 0],
[1, 0, 1, 0],
[0, 0, 0, 0]
]
start = (0, 0)
end = (3, 3)
print(shortest_path_grid(grid, start, end)) # 66. 트러블슈팅
문제 1: 무한 루프 (방문 체크 누락)
증상:
def dfs_wrong(graph, node):
print(node)
for neighbor in graph[node]:
dfs_wrong(graph, neighbor) # visited 체크 없음
# 사이클 있는 그래프에서 무한 재귀해결:
def dfs_correct(graph, node, visited):
if node in visited:
return
visited.add(node)
print(node)
for neighbor in graph[node]:
dfs_correct(graph, neighbor, visited)문제 2: 방향 vs 무방향 혼동
증상:
# 무방향 그래프인데 한쪽만 추가
graph = {1: [2], 2: [3], 3: []}
# 1 → 2는 가능, 2 → 1은 불가능 (잘못됨)해결:
# 무방향 그래프: 양방향 추가
def add_edge_undirected(graph, a, b):
graph[a].append(b)
graph[b].append(a)
# 방향 그래프: 한쪽만 추가
def add_edge_directed(graph, a, b):
graph[a].append(b)문제 3: 1-indexed vs 0-indexed
증상:
# 문제: 정점 1~N
# 코드: 0-indexed 사용
graph = {i: [] for i in range(n)} # 0~N-1
# 정점 N이 누락됨해결:
# 1-indexed
graph = {i: [] for i in range(1, n + 1)}
# 또는 0-indexed로 통일
edges = [[a - 1, b - 1] for a, b in edges]문제 4: 메모리 초과 (인접 행렬)
증상:
n = 100000
matrix = [[0] * n for _ in range(n)]
# MemoryError: 10^10 크기 배열해결: 인접 리스트 사용
graph = {i: [] for i in range(n)}
# O(V + E) 공간마무리
그래프 자료구조는 연결 관계를 표현하는 가장 일반적인 구조입니다.
핵심 요약
-
표현
- 인접 리스트: 희소 그래프 (O(V+E))
- 인접 행렬: 밀집 그래프 (O(V²))
-
탐색
- BFS: 최단 경로, 큐 사용
- DFS: 모든 경로, 스택 사용
-
응용
- 연결 요소, 사이클 감지, 위상 정렬
선택 가이드
| 상황 | 표현 | 탐색 |
|---|---|---|
| 간선 적음 (E << V²) | 인접 리스트 | BFS/DFS |
| 간선 많음 (E ≈ V²) | 인접 행렬 | BFS/DFS |
| 최단 경로 | 인접 리스트 | BFS |
| 모든 경로 | 인접 리스트 | DFS |
| 간선 확인 빈번 | 인접 행렬 | - |
추천 문제
백준:
LeetCode:
다음 단계
- BFS와 DFS 상세: BFS와 DFS 완벽 정리
- 트리 자료구조: 트리 완벽 정리
- 백트래킹: 백트래킹 완벽 정리
그래프는 실생활 문제를 모델링하는 핵심 도구입니다. BFS와 DFS를 마스터하면 대부분의 그래프 문제를 해결할 수 있습니다.