그래프(Graph)
- vertex(정점)과 edge(간선)으로 이루어진 자료구조
- 프로그래밍에서 이를 표현하는 방식으로는
인접 행렬과인접 리스트가 있다.
인접 행렬
2차원 배열로 그래프의 연결 관계를 표현
INF = 987654321
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
# 0과 1의 연결 관계
graph[0][1] ( == graph[1][0])인접 리스트
연결 리스트 자료구조로 그래프의 연결 관계 표현
파이썬에서는 일반 리스트 자료형이 연결 리스트의 역할을 하므로 다음과 같이 구현한다.
vertex = 3
graph = [[] for i in range(vertex)]
# 0번 간선과의 연결 정보
graph[0].append((1, 7))
graph[0].append((2, 5))
# 1번 간선과의 연결 정보
graph[1].append((0, 7))
# 2번 간선과의 연결 정보
graph[2].append((0, 5))
# 0번과 1번의 연결 관계
for i in graph[0]:
if i[0] == 1:
print(i[1])인접 행렬 vs 인접 리스트
인접 행렬
- 장점: 두 노드 간 연결 여부 확인이 쉽고 정보를 얻는 속도가 빠름
- 단점: 불필요한 메모리 낭비
인접 리스트
- 장점: 메모리를 효율적으로 사용 (자기 자신과의 관계 저장 X, 필요한 노드의 관계만 저장)
- 단점: 연결 여부 확인을 위해 순회를 해야 한다. (정보 얻는 속도 느림)
따라서 노드의 개수에 비해 간선이 확연히 적을 때(sparse graph)에는 인접 리스트,
아닌 경우에는 인접 행렬을 사용하는 것이 좋다.