그래프는 정점 (Node)과 정점 사이를 연결하는 간선 (Edge)으로 이루어진 비선형 자료구조이다.

1. 정점은 여러개의 간선을 가질 수 있다.

2. 방향 그래프 & 무방향 그래프로 나눌 수 있다.
   방향 그래프 : 간선으로 이어진 정점끼리 양방향 이동이 가능 (A,B) = (B,A)
   무방향 그래프 : 양방향으로 갈 수 있어도 (A,B)와 (B,A)는 다른 간선으로 취급된다.

3. 간선은 가중치를 가질 수 있다.

4. 사이클이 발생할 수 있다. (탐색 시 무한 루프에 빠지지 않도록 사이클을 찾아야 함)
   사이클은 그래프의 부분 집합에서 순환되는 부분이다.

---

그래프의 구현

2차원 배열과 인접 리스트 2가지 방식으로 그래프를 표현할 수 있다.

1. 2차원 배열

정점의 수 n에 대해 n x n 2차원 배열을 만들고 연결이 안된 상태 false로 초기화한다.
행렬의 행 부분을 시작 정점, 열 부분을 도착 정점으로 두고 간선이 연결된 정점에 대해 true 값을 넣어주면 된다.

1. 무방향 그래프의 경우 대각선을 기준으로 대칭을 이룬다는 특징이 있다.
2. 2차원 배열은 자주 사용하지 않는 방식인데, 그 이유는 존재하지 않는 간선에 대한 정보까지도 저장하기 때문에 비효율적이다.
3. 간선에 가중치가 존재한다면 Array[i][j]에 true, false 대신 가중치 값을 넣어주면 된다.
   

const graph = Array.from(Array(5),() => Array(5).fill(false))
graph[0][1] = true 
graph[0][3] = true
graph[1][2] = true // 이하 생략 

2. 인접 리스트

정점의 수 n만큼 배열을 만든 후, 연결할 정점을 배열에 추가하면 된다.

const graph = Array.from(Array(5),() => [])
graph[0].push(1)
graph[0].push(3)
graph[1].push(2) // 이하 생략