간단하게 그래프를
javascript로 구현해보고, 상황별 장단점을 분석해본다.
개요
여기 이 그림을 코드를 이용해서 저장해달라고 하면 어떻게 해야 할까 ?
어떤 데이터 구조를 사용해야 제대로 된 도움을 받을 수 있을까 ?
위와 같은 데이터 구조는 오늘날 전세계에서 정말 유용하게 쓰이고 있다.
즉, 그래프는 기본적으로 모든 sns에서 사용되는데, 사용자 추천 엔진 등을 만들 때 사용된다.
예를 들어 넷플릭스가 새로운 영화 등을 추천하거나 구글 지도의 길 찾기와 같은 것들은 그래프 구조를 기반으로 만들어 진다.
그렇다면 이 그래프 구조는 어떻게 만들 수 있을까, 클래스를 직접 만들어야 할까 ?
나누어서 생각해 보면 실제로 그래프를 저장할 때 중요한 정보는 노드, 즉 실제 정점들과 연결을 저장하는 방식이다.
연결 리스트는 next와 previous를 이용하여 정보의 연결을 저장했고 이진 탐색 트리에서는 left와 right가 노드 내부에 존재하여 저장을 하는 방식을 따랐다.
그렇지만 그래프는 노드의 개수나 노드 사이의 연결인 간선의 개수가 정해져 있지 않기 때문에 위와 같은 방법을 쓸 수 없다.
연결 리스트를 저장할 때는 배열을 사용할 수 있었다. 이는 그래프도 마찬가지이다(물론 더 무거운 방식의 접근법을 사용해도 된다).
이번 포스팅에서 우리는 대부분의 문서나 블로그, 스택오버플로우에 나오는 가장 흔한 두 가지 방법으로 그래프 구조를 자바스크립트로 직접 구현해보도록 한다.
이 두 방법의 이름은 인접 행렬과 인접 리스트라고 한다.
바로 들어가보기 전에, 우리가 작업하고자 하는 그래프의 예시를 우선 보도록 하자.
맨 위의 그림보다는 좀 많이 간소화된 것 같지만 가지고 있어야 할 개념은 동일하다.
정점과 간선이 존재한다. A와 B 사이, A와 F 사이에 있는 간선들처럼 말이다. 그리고 우린 이 정보를 저장해야 한다.
그러면 인접 행렬부터 다뤄보자.
행렬을 잘 모를 수 있다. 행렬은 이차원 구조로 항상은 아니지만 보통 중첩 행렬로 표현된다.
기본적으로 행과 열에 맞춰서 정보를 저장한다. 그래서 위의 그래프의 연결들을 행렬을 사용하면 다음과 같이 표현할 수 있다.
이는 불린 행렬, 즉 예 아니오 또는 0 1로 표현되게 된다.
우리는 두 개의 노드, 즉 정점 사이를 보는 것이다. 예를 들어 A와 D가 연결이 되어 있다면 1로 표시하겠지만 실제로는 연결이 되어 있지 않기 때문에 0으로 표시한다. 즉 0으로 표시하는 것은 간선이 존재하지 않는다를 뜻한다.
위의 그래프는 무방향 그래프이다. 즉 양방향으로 연결이 되어있다는 말이다. 그렇지만 한 방향으로의 연결만 저장해서 방향 그래프를 저장할 수도 있다.
두번째로 다룰 접근법은 인접 리스트라고 한다. 노드들을 숫자로 바꾼 그래프의 모습을 보자. 이제 A, B, C, D, E, F 대신 0, 1, 2, 3, 4, 5를 가지고 있다.
이를 인접 리스트로 표현하면 다음과 같다.
배열 리스트를 가지고 간선을 저장하는 방식이다.
만약 3과 다른 노드, 정점들 사이에 존재하는 간선을 확인하고 싶다면 배열의 인덱스 3으로 가서 확인하는 방식이다.
그렇다면 글자를 다뤄야 하는 경우가 있는데, 앞으로 돌아가보자. 여기에서는 A, B, C, D, E, F처럼 글자를 다뤄야 한다.
만약 그래프가 숫자보다 더 자의적인 것들, 예를 들어 이름이나 스트링 같이 숫자가 아닌 것들을 다룬다고 해보자.
이러한 상황처럼 순서를 가지지 않는 방식이라면 배열을 통한 저장 방식이 아닌 해시 테이블을 사용하여 그래프 구조를 저장한다.
A의 간선들을 보고 싶다면 위 구조 안에 포함되어있는 A를 확인하면 된다. A는 B와 F와 연결되어있는 간선을 가지고 있는 것을 확인할 수 있다.
구현
인접 리스트를 사용하여 그래프(양방향)를 구현한다.
class Graph {
constructor() {
this.adjacencyList = {}
}
addVertex(vertex) { // 단순히 정점을 인접 리스트에 추가해준다. 정점의 이름을 인접 리스트의 키로 입력하고 값은 빈 배열로 설정해준다.
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
addEdge(v1, v2) { // 두 개의 정점간의 간선 정보를 저장해준다.
// ... 실제 코드라면 에러 처리 코드를 추가해준다.
// 방향 그래프를 만들고자 할때는 양 정점에 각각을 저장하지 않고 한 쪽에만 저장해주어 순서를 만들어주면 된다.
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
removeEdge(v1, v2) { // 두 개의 정점간의 간선 정보를 삭제해준다.
// ... 실제 코드라면 에러 처리 코드를 추가해준다.
this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
this.adjacencyList[v2] = this.adjacencyList[v1].filter(v => v !== v1);
}
removeVertex(vertex) { // 인자로 받은 정점을 제거해준다. 또한 이 정점과 연결되어있는 모든 간선들도 제거해준다.
// ... 실제 코드라면 에러 처리 코드를 추가해준다.
while(this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex)
}
delete this.adjacencyList[vertex];
}
bfs(start_vertex = "A") {
const queue = [start_vertex];
const result = [];
const visited = {};
let currentVertex;
visited[start_vertex] = true;
while(queue.length) {
currentVertex = queue.shift();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if(!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return result;
}
dfs(start_vertex = "A") {
const stack = [start_vertex];
const result = [];
const visited = {};
let currentVertex;
visited[start] = true;
while(stack.length) {
currentVertex = stack.pop();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if(!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return result;
}
recursive_dfs(start_vertex) {
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
(function dfs(vertex) {
if(!vertex) return null;
visited[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach(neighbor => {
if(!visited[neighbor]) {
return dfs(neighbor);
}
});
})(start_vertex);
return result;
}
}