그래프

트리에선 존재할 수 없는 사이클이 존재
트리 ⊂ 그래프

Vertex(A,B) (=node) 정점 : 위치
Edge 간선 : 위치 간의 관계
Direction 방향
Weight 가중치

그래프 종류

https://laboputer.github.io/ps/2017/09/29/graph/

그래프 표현

인접 리스트

ex) dict= {'A' = [B, C], 'B' = [A, C] , 'C' = [A, B, D] , 'D' = [C] }
장점: 접근이 빠르다.
단점: 0이 많을수록 쓸데없이 공간 차지를 한다(=희소행렬)

인접 행렬

2차원 배열(NxN)로 정점 간의 간선의 존재 여부를 1 또는 0
ex)
  A B C D
A 0 1 1 0
B 1 0 1 0
C 1 1 0 1
D 0 0 1 0

문제 특성에 맞게 인접 리스트 혹은 인접 행렬을 선택해야 한다