그래프
그래프는 노드(node)와 간선(edge)로 표현되며 이때 노드를 정점(vertex)이라고도 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다.
프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다.
- 인접 행렬(Adjacent Matrix)
- 인접 리스트(Adjacent Lint)
인접 행렬
2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 파이썬에서는 리스트를 사용한다. 연결되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다.
인접 행렬 방식 예제
INF=999999999 # 무한의 비용 선언
# 2차원 리스트를 이용해 인접 행렬 표현
graph=[
[0,7,5],
[7,0,INF],
[5,INF,0]
]
인접 리스트
각 노드에 대해 인접한 노드를 차례대로 연결하여 저장한다. C++나 자바와 같은 프로그래밍 언어에서는 별도의 연결 리스트 기능을 위한 표준 라이브러리를 사용한다. 반면에 파이썬은 리스트 자료형이 append()와 여러 메서드를 제공하므로 역시 단순히 2차원 리스트를 사용해 인접 리스트를 구현할 수 있다.
인접 리스트 방식 예제
# 행이 3개인 2차원 리스트로 인접 리스트 표현
graph=[[] for _ in range(3)]
# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))
# 노드 1에 연결된 노드 정보 저장
graph[1].append((0,7))
# 노드 2에 연결된 노드 정보 저장
graph[2].append((0,5))
두 방식은 어떤 차이가 있을까?
메모리 측면에서 보자면 인접 행렬 방식은 인접 리스트 방식에 비해 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.
하지만 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
'python > python' 카테고리의 다른 글
우선순위 큐 (0) | 2021.02.09 |
---|---|
이진 탐색 트리 (0) | 2021.02.09 |
재귀함수 (0) | 2021.02.09 |
스택 & 큐 (0) | 2021.02.09 |
Python 문법 (0) | 2021.01.02 |