그래프(Graph) 란?

연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조

연결 관계에 초점이 맞춰져 있다

노드(Node) : 연결 관계를 가진 각 데이터를 의미. 정점(Vertex) 라고도 함
간선(Edge) : 노드 간의 관계를 표시한 선
인접노드(Ajdacent Node) : 간선으로 직접 연결된 노드(또는 정점)

유방향 그래프 : 방향이 있는 간선을 갖는다. 각 간선은 한 방향으로만 진행
무방향 그래프 : 방향이 없는 간선을 갖는다.

---

그래프의 표현 방법

1. 인접행렬

	A	B	C	D
A	X	O	O	X
B	O	X	X	X
C	O	X	X	O
D	X	X	O	X

이 행렬을 2차원 배열로 나타내면?

graph = [
	[False, True, True, False],
    [True, False, False, False],
    [True, False, False, True],
    [False, False, True, False],
]

2. 인접 리스트

A -> B -> C
B -> A
C -> A -> D
D -> C

이를 딕셔너리로 표현하면?

graph = {
	A: [B,C],
    B: [A],
    C: [A,D],
    D: [C]
}

🔍 두 방식의 차이 : 시간 vs 공간!