그래프 개념 그래프 용어 그래프의 종류 그래프 표현 방식 인접 행렬 vs 인접 리스트 비교 그래프 구현 코드 실전 활용 예시
그래프(Graph) 는 노드(Node) 와 간선(Edge) 으로 이루어진 자료구조로, 객체 간의 연결 관계 를 표현하는 데 사용된다.
"연결"이라는 단어가 나오면 그래프 를 떠올려라!
네트워크 구조를 표현하는 데 적합
방향이 있을 수도 있고, 없을 수도 있음
순환(Cycle)이 있을 수도 있고, 없을 수도 있음
트리(Tree)는 그래프의 특수한 형태 (사이클이 없는 연결 그래프)
구분
그래프
트리
방향성
방향/무방향 모두 가능
방향 그래프
순환
순환 가능
순환 없음
루트
루트 개념 없음
루트 노드 존재
부모-자식
없음
있음
간선 수
제한 없음
N-1개 (N: 노드 수)
용어
영어
설명
노드 Vertex (Node)
그래프의 기본 단위, 정점이라고도 함
간선 Edge
노드와 노드를 연결하는 선
가중치 Weight
간선에 부여된 값 (비용, 거리 등)
인접 Adjacent
두 노드가 간선으로 직접 연결된 상태
경로 Path
한 노드에서 다른 노드까지 거치는 노드들의 순서
차수 Degree
노드에 연결된 간선의 수
용어
설명
진입 차수 (In-degree) 해당 노드로 들어오는 간선의 수
진출 차수 (Out-degree) 해당 노드에서 나가는 간선의 수
1 ─── 2
│ \ │
│ \ │
3 ─── 4
노드(Vertex) : 1, 2, 3, 4간선(Edge) : (1,2), (1,3), (1,4), (2,4), (3,4)노드 1의 차수 : 3 (2, 3, 4와 연결)
무방향 그래프 (Undirected Graph)
간선에 방향이 없음
(A, B)와 (B, A)는 같은 간선
양방향 이동 가능
방향 그래프 (Directed Graph, Digraph)
간선에 방향이 있음
(A, B)와 (B, A)는 다른 간선
화살표 방향으로만 이동 가능
A ──5── B
│ │
3 2
│ │
C ──4── D
간선에 비용(가중치)이 있음
최단 경로 문제에서 주로 사용
비가중치 그래프 (Unweighted Graph) A ───── B
│ │
│ │
C ───── D
종류
설명
연결 그래프 모든 노드가 연결되어 있음
비연결 그래프 연결되지 않은 노드가 존재
완전 그래프 모든 노드가 서로 연결
순환 그래프 사이클이 존재
비순환 그래프 사이클이 없음 (DAG: Directed Acyclic Graph)
4.1 인접 행렬 (Adjacency Matrix) 2차원 배열 을 사용하여 노드 간의 연결 관계를 표현하는 방식
matrix[i][j] = 1 : 노드 i에서 노드 j로 가는 간선이 존재matrix[i][j] = 0 : 간선이 존재하지 않음가중치 그래프: matrix[i][j] = weight
0 ─── 1
│ \ │
│ \ │
2 ─── 3
인접 행렬 표현:
0
1
2
3
0
0
1
1
1
1
1
0
0
1
2
1
0
0
1
3
1
1
1
0
# 인접 행렬 표현
INF = float ('inf' ) # 무한대 (연결되지 않음)
# 가중치가 없는 경우
matrix = [
[0 , 1 , 1 , 1 ], # 노드 0
[1 , 0 , 0 , 1 ], # 노드 1
[1 , 0 , 0 , 1 ], # 노드 2
[1 , 1 , 1 , 0 ] # 노드 3
]
# 가중치가 있는 경우
weighted_matrix = [
[0 , 7 , 5 , INF ],
[7 , 0 , INF , 2 ],
[5 , INF , 0 , 3 ],
[INF , 2 , 3 , 0 ]
]4.2 인접 리스트 (Adjacency List) 리스트 를 사용하여 각 노드에 연결된 노드들을 저장하는 방식
각 노드마다 연결된 노드들의 리스트를 저장
가중치 그래프: (연결된 노드, 가중치) 형태의 튜플 저장
# 인접 리스트 표현 (리스트 방식)
graph = [
[1 , 2 , 3 ], # 노드 0 -> 1, 2, 3과 연결
[0 , 3 ], # 노드 1 -> 0, 3과 연결
[0 , 3 ], # 노드 2 -> 0, 3과 연결
[0 , 1 , 2 ] # 노드 3 -> 0, 1, 2와 연결
]
# 인접 리스트 표현 (딕셔너리 방식)
graph_dict = {
0 : [1 , 2 , 3 ],
1 : [0 , 3 ],
2 : [0 , 3 ],
3 : [0 , 1 , 2 ]
}
# 가중치가 있는 인접 리스트
weighted_graph = [
[(1 , 7 ), (2 , 5 )], # 노드 0
[(0 , 7 ), (3 , 2 )], # 노드 1
[(0 , 5 ), (3 , 3 )], # 노드 2
[(1 , 2 ), (2 , 3 )] # 노드 3
]
구분
인접 행렬
인접 리스트
메모리 복잡도 O(V^2)
O(V + E)
간선 존재 확인 O(1)
O(degree)
모든 간선 순회 O(V^2)
O(V + E)
간선 추가 O(1)
O(1)
간선 삭제 O(1)
O(degree)
희소 그래프 비효율적
효율적
밀집 그래프 효율적
비효율적
구현 난이도 쉬움
보통
V : 노드(정점)의 수, E : 간선의 수
노드 수가 적고, 간선이 많은 밀집 그래프
두 노드 간 연결 여부를 빠르게 확인 해야 할 때
플로이드-워셜 알고리즘 등 모든 쌍의 최단 경로 계산
# 인접 행렬 - 연결 확인 O(1)
if matrix [i ][j ]:
print (f"노드 { i } { j } )
간선이 적은 희소 그래프 (대부분의 실제 그래프)
DFS, BFS 탐색 시 인접 노드 순회다익스트라 알고리즘 등 최단 경로 계산메모리 효율이 중요한 경우
# 인접 리스트 - 인접 노드 순회
for neighbor in graph [node ]:
print (f"노드 { node } { neighbor } )노드 1000개, 간선 2000개인 희소 그래프:
방식
메모리 사용
인접 행렬
1,000,000 (1000 x 1000)
인접 리스트
약 4,000 (1000 + 2000 x 2)
class GraphMatrix :
def __init__ (self , num_vertices ):
"""그래프 초기화 (인접 행렬)"""
self .V = num_vertices
self .matrix = [[0 ] * num_vertices for _ in range (num_vertices )]
def add_edge (self , u , v , weight = 1 ):
"""간선 추가 (무방향 그래프)"""
self .matrix [u ][v ] = weight
self .matrix [v ][u ] = weight # 무방향이므로 양쪽 추가
def add_directed_edge (self , u , v , weight = 1 ):
"""간선 추가 (방향 그래프)"""
self .matrix [u ][v ] = weight
def remove_edge (self , u , v ):
"""간선 제거"""
self .matrix [u ][v ] = 0
self .matrix [v ][u ] = 0
def has_edge (self , u , v ):
"""간선 존재 여부 확인"""
return self .matrix [u ][v ] != 0
def get_neighbors (self , v ):
"""인접 노드 리스트 반환"""
neighbors = []
for i in range (self .V ):
if self .matrix [v ][i ] != 0 :
neighbors .append (i )
return neighbors
def print_matrix (self ):
"""인접 행렬 출력"""
print ("인접 행렬:" )
for row in self .matrix :
print (row )
# 사용 예시
if __name__ == "__main__" :
# 5개의 노드를 가진 그래프 생성
g = GraphMatrix (5 )
# 간선 추가
g .add_edge (0 , 1 )
g .add_edge (0 , 2 )
g .add_edge (1 , 2 )
g .add_edge (1 , 3 )
g .add_edge (2 , 4 )
# 인접 행렬 출력
g .print_matrix ()
# 출력:
# [0, 1, 1, 0, 0]
# [1, 0, 1, 1, 0]
# [1, 1, 0, 0, 1]
# [0, 1, 0, 0, 0]
# [0, 0, 1, 0, 0]
# 간선 확인
print (f"0-1 연결: { g .has_edge (0 , 1 )} ) # True
print (f"0-3 연결: { g .has_edge (0 , 3 )} ) # False
# 인접 노드
print (f"노드 1의 인접 노드: { g .get_neighbors (1 )} ) # [0, 2, 3] from collections import defaultdict
class GraphList :
def __init__ (self , directed = False ):
"""그래프 초기화 (인접 리스트)"""
self .graph = defaultdict (list )
self .directed = directed
def add_edge (self , u , v , weight = 1 ):
"""간선 추가"""
self .graph [u ].append ((v , weight ))
if not self .directed :
self .graph [v ].append ((u , weight )) # 무방향이면 양쪽 추가
def remove_edge (self , u , v ):
"""간선 제거"""
self .graph [u ] = [(node , w ) for node , w in self .graph [u ] if node != v ]
if not self .directed :
self .graph [v ] = [(node , w ) for node , w in self .graph [v ] if node != u ]
def has_edge (self , u , v ):
"""간선 존재 여부 확인"""
for node , _ in self .graph [u ]:
if node == v :
return True
return False
def get_neighbors (self , v ):
"""인접 노드 리스트 반환"""
return [node for node , _ in self .graph [v ]]
def get_neighbors_with_weight (self , v ):
"""인접 노드와 가중치 반환"""
return self .graph [v ]
def print_graph (self ):
"""인접 리스트 출력"""
print ("인접 리스트:" )
for node in sorted (self .graph .keys ()):
print (f"{ node } { self .graph [node ]} )
# 사용 예시
if __name__ == "__main__" :
# 무방향 그래프 생성
g = GraphList (directed = False )
# 간선 추가
g .add_edge (0 , 1 , 5 )
g .add_edge (0 , 2 , 3 )
g .add_edge (1 , 2 , 2 )
g .add_edge (1 , 3 , 6 )
g .add_edge (2 , 4 , 4 )
# 인접 리스트 출력
g .print_graph ()
# 출력:
# 0: [(1, 5), (2, 3)]
# 1: [(0, 5), (2, 2), (3, 6)]
# 2: [(0, 3), (1, 2), (4, 4)]
# 3: [(1, 6)]
# 4: [(2, 4)]
print (f"노드 1의 인접 노드: { g .get_neighbors (1 )} ) # [0, 2, 3] # 패턴 1: 인접 리스트 초기화 (가장 많이 사용)
n = 5 # 노드 개수
graph = [[] for _ in range (n + 1 )] # 1-indexed
# 간선 입력 받기
edges = [(1 , 2 ), (1 , 3 ), (2 , 4 ), (3 , 4 ), (4 , 5 )]
for a , b in edges :
graph [a ].append (b )
graph [b ].append (a ) # 무방향 그래프
print (graph )
# [[], [2, 3], [1, 4], [1, 4], [2, 3, 5], [4]]
# 패턴 2: 가중치 있는 그래프
weighted_edges = [(1 , 2 , 5 ), (1 , 3 , 3 ), (2 , 4 , 2 )]
weighted_graph = [[] for _ in range (n + 1 )]
for a , b , cost in weighted_edges :
weighted_graph [a ].append ((b , cost ))
weighted_graph [b ].append ((a , cost ))
# 패턴 3: 인접 행렬 초기화
INF = float ('inf' )
matrix = [[INF ] * (n + 1 ) for _ in range (n + 1 )]
# 자기 자신으로의 비용은 0
for i in range (n + 1 ):
matrix [i ][i ] = 0
# 간선 정보 입력
for a , b , cost in weighted_edges :
matrix [a ][b ] = cost
matrix [b ][a ] = cost # 무방향
문제 유형
적합한 표현
적합한 알고리즘
최단 경로 (양수 가중치)
인접 리스트
다익스트라
최단 경로 (음수 가중치)
인접 리스트
벨만-포드
모든 쌍 최단 경로
인접 행렬
플로이드-워셜
연결 요소 찾기
인접 리스트
DFS/BFS
사이클 탐지
인접 리스트
DFS
위상 정렬
인접 리스트
DFS/BFS (Kahn)
최소 신장 트리
인접 리스트
크루스칼/프림
def count_connected_components (n , edges ):
"""
연결 요소의 개수를 반환
n: 노드 개수
edges: 간선 리스트 [(a, b), ...]
"""
# 인접 리스트 생성
graph = [[] for _ in range (n + 1 )]
for a , b in edges :
graph [a ].append (b )
graph [b ].append (a )
visited = [False ] * (n + 1 )
count = 0
def dfs (node ):
visited [node ] = True
for neighbor in graph [node ]:
if not visited [neighbor ]:
dfs (neighbor )
# 모든 노드 순회
for i in range (1 , n + 1 ):
if not visited [i ]:
dfs (i )
count += 1
return count
# 테스트
n = 6
edges = [(1 , 2 ), (2 , 3 ), (4 , 5 )] # 3개의 연결 요소: {1,2,3}, {4,5}, {6}
print (count_connected_components (n , edges )) # 3 from collections import deque
def has_path (n , edges , start , end ):
"""
start에서 end로 가는 경로가 존재하는지 확인
"""
if start == end :
return True
# 인접 리스트 생성
graph = [[] for _ in range (n + 1 )]
for a , b in edges :
graph [a ].append (b )
graph [b ].append (a )
# BFS로 경로 탐색
visited = [False ] * (n + 1 )
queue = deque ([start ])
visited [start ] = True
while queue :
node = queue .popleft ()
for neighbor in graph [node ]:
if neighbor == end :
return True
if not visited [neighbor ]:
visited [neighbor ] = True
queue .append (neighbor )
return False
# 테스트
n = 5
edges = [(1 , 2 ), (2 , 3 ), (4 , 5 )]
print (has_path (n , edges , 1 , 3 )) # True
print (has_path (n , edges , 1 , 5 )) # False
그래프 = 노드(Vertex) + 간선(Edge) 문제에서 "연결"이 나오면 그래프를 떠올려라
인접 행렬 : O(V^2) 메모리, 간선 확인 O(1) - 밀집 그래프에 적합인접 리스트 : O(V+E) 메모리, 순회 효율적 - 희소 그래프에 적합코딩테스트에서는 대부분 인접 리스트 사용
1-indexed 그래프는 [[] for _ in range(n + 1)] 패턴 사용