그래프를 구현하는 방식에는 크게 두 가지가 있는데, 인접 리스트와 인접 행렬이다.
인접리스트(Adjacency List)
- 인접 리스트는 그래프의 전체 노드 목록을 저장한다.
- Python에서는 하나의 노드가 키(key)가 되고, 그 노드에 인접한 노드가 값(value)이 되는 딕셔너리로 구현할 수 있다.
예시 코드) 위 그림을 Python 딕셔너리로 구현한 인접리스트
class Graph:
def __init__(self):
self.vertices = {
"A": {"B"}, # 여기서 {"B"}가 set의 형태이다.
"B": {"C", "D"}, # {"B" : {}}의 형태는 딕셔너리
"C": {"E"}, # 즉, 딕셔너리 안에 set이 있는 것이다.
"D": {"F", "G"},
"E": {"C"},
"F": {"C"},
"G": {"A", "F"}
}- set을 활용하는 이유는 한 노드에 인접한 인접 노드들끼리는 순서를 정할 필요가 없기 때문이다.
인접 리스트의 장점
하나의 노드에서 O(1), 즉 상수시간에 각 간선(edge)에 접근할 수 있다.
예를 들어, A-G를 연결하는 간선이 있는지 알고 싶다면 딕셔너리에서 A라는 key값으로 접근했을 때 G가 value에 포함되어 있는지만 확인하면 된다.
→ edge가 set에 포함되어 있기 때문에 O(1) 상수 시간에 edge가 있는지 확인할 수 있다.
인접행렬(Adjacency Matrix)
위의 그림에서 각 노드에 연결된 간선들이 향하는 방향을 아래와 같이 행렬로 표현할 수 있다. 예를 들어, A→B로 향하는 간선이 있다면 A행과 B열이 교차되는 지점에 1을 표시할 수 있다. (행은 시작 지점 기준, 열은 도착 지점을 기준으로 표시하게 된다.)
즉, 행노드와 연결되는 열노드에 대해서 1 값이 된다.
예시 코드) 위 그림을 2차원 리스트로 구현한 인접행렬
# 간선 가중치는 1이다.
class Graph:
def __init__(self):
self.edges = [[0,1,0,0,0,0,0],
[0,0,1,1,0,0,0],
[0,0,0,0,1,0,0],
[0,0,0,0,0,1,1],
[0,0,1,0,0,0,0],
[0,0,1,0,0,0,0],
[1,0,0,0,0,1,0]]위에서 행렬은 리스트 안에 리스트가 있는 2차원 리스트로 표현된다. (0은 두 노드 사이에 간선이 없음을 나타낸다.)
이 때 간선 가중치(edge weights)가 있는 그래프라면, 0보다 큰 수로 표시된 숫자에 한해 간선 가중치를 알 수 있다. 그래프에 가중치가 없을 경우 1은 단순히 간선이 있다는 것을 표현한다.
만약 왼쪽 그림과 같이 간선에 방향이 없는(무향) 그래프를 인접 행렬로 표현하면, 오른쪽과 같이 대각선을 기준으로 대칭인 행렬로 표현된다. 이는 1→2로 향하는 간선이 존재할 때 2→1로 향하는 간선 역시 반드시 존재하기 떄문이다.
레퍼런스
- https://sarah950716.tistory.com/12 (인접 행렬 그림 출처)
- 코드스테이츠 AIB Section 3 자료 - [그래프의 활용]
Data Engineer 🍊