[자료구조와 알고리즘] Graph - 그래프

ESH'S VELOG·2024년 8월 10일

algorithm

목록 보기

4/4

그래프 G(V, E)

📜 정의

vertex 와 edge 로 이루어진 집합

그림을 참고하여 동그라미(정점)는 vertex, 선(간선)은 edge로 볼 수 있다.

트리 구조에 비해 방향성을 가지고 있다(트리는 단방향 그래프의 특징을 가지고있다고 볼 수 있다)

예시) 지도 네비게이션, 인스타그램 친구 관계, 항공 운송망 등

⚖️ 특징

1. N개의 정점을 가지면 $O(N^2)$ 의 공간 복잡도를 갖는다.
2. 코드로는 2차원 배열, 연결 리스트로 표현가능하다.
3. 2차원 배열 경우

쿼리를 추가 or 제거 시 O(1)의 시간이 소요된다.
간선 수가 적을 경우 메모리가 낭비된다.

연결 리스트의 경우

공간의 낭비를 막고, 효율적으로 그래프를 저장
정점은 배열에 저장하고, 간선의 가중치는 연결리스트의 노드에 저장한다.

💻 Javascript 표현

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 ] }

🛒 그래프의 종류

무방향 그래프

위 그림은 양방향 그래프로도 볼 수 있다.
따라서 1번 vertex는 2번, 3번으로 갈 수 있고, 2번 vertex는 1번, 4번, 5번을 갈 수 있다.
위의 vertex간 데이터를 나열해보면 다음과 같다.
- [1 <-> 2], [1 <-> 3], [2 <-> 4], [2 <-> 5], [3 <-> 4]