- vertex 와 edge 로 이루어진 집합
- 그림을 참고하여 동그라미(정점)는 vertex, 선(간선)은 edge로 볼 수 있다.
- 트리 구조에 비해 방향성을 가지고 있다(트리는 단방향 그래프의 특징을 가지고있다고 볼 수 있다)
- 예시) 지도 네비게이션, 인스타그램 친구 관계, 항공 운송망 등
1. N개의 정점을 가지면 의 공간 복잡도를 갖는다.
2. 코드로는 2차원 배열, 연결 리스트로 표현가능하다.
3. 2차원 배열 경우
// 출발 -> 도착을 배열에 넣고,
const direction = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 5]]
// vertex 수 + 1 길이의 배열을 생성 : 배열은 0번 부터 시작하므로 1부터 입력해주기 위함
const graph = Array.from(Array(6), Array(6).fill(0))
for(const [a, b] of direction) {
// 그래프에 가중치가 없다면 1로 표시한다. 가중치가 있으면 그 값을 넣어주면 된다.
graph[a][b] = 1
}
console.log(graph)
// [
// [ 0, 0, 0, 0, 0, 0 ],
// [ 0, 0, 1, 1, 1, 0 ],
// [ 0, 1, 0, 1, 0, 1 ],
// [ 0, 0, 0, 0, 1, 0 ],
// [ 0, 0, 1, 0, 0, 1 ],
// [ 0, 0, 0, 0, 0, 0 ]
// ]
const direction = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 5]]
const list = {};
for (const [a, b] of arr) {
if (!list[a]) list[a] = [];
list[a].push(b);
}
console.log(list)
// { '1': [ 2, 3, 4 ], '2': [ 1, 3, 5 ], '3': [ 4 ], '4': [ 2, 5 ] }