자바스크립트의 자료구조 6 : 그래프(Graphs)

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

1. 그래프(Graphs)란?

각 노드들이 서로 연결되어 있는 자료 구조형으로, 아주 커다란 자료 구조형의 범위 중 하나이다. 실제로 그래프 자료 구조 안에 Trees 자료구조가 포함되어 있고, Trees 안에는 Linked List가 포함되어 있다. 즉, 그래프는 이들을 모두 포괄하고 있는 자료 구조형인 것이다.

Graphs

 

그래프 자료구조를 묘사하는 방식에는 크게 3가지 방식이 있다.

 

# Directed vs. Undirected Graphs

directed graphs는 edge가 일방향적인 반면, undirected graphs는 edge가 쌍방향적이다. 사용처에 대한 예시를 들자면, 트위터와 페이스북을 예시로 들 수 있다. 트위터의 경우 한 사용자가 다른 사용자를 팔로우 한다고 해도, 자동적으로 상호 팔로우가 되지는 않는다. 반면 페이스북은 한 사용자가 다른 사용자와 친구를 맺으면 상호 친구가 맺어진다. 이 경우 트위터는 directed graphs를, 페이스북은 undirected graphs를 사용한다고 볼 수 있다.

undirected vs. directed

 

# Weighted vs. Unweighted

weighted graphs는 노드 외에 edge에도 데이터가 있는 형태이다. google map이 특정 장소를 방문할 최단거리를 찾을 경우처럼, 최적의 경로를 찾는 경우에 weighted graphs를 많이 사용한다고 한다.

unweighted vs. weighted

 

# Cyclic vs. Acyclic

각 노드 간의 연결이 서로 순환된 형태일 경우 cyclic, 아닐 경우 acyclic한 graph이다.

Cyclic vs. Acyclic

 

# Directed Acyclic Graphs(DAG)

위 세가지 개념을 혼합한 그래프 종류 중 하나로 Directed Acyclic Graphs가 있다. 블록체인 같은 곳에서 이러한 자료구조형을 주로 사용한다.

Directed Acyclic Graphs

 

2. Graphs Implementation

위와 같은 형태의 graphs를 만든다고 하면, 아래 3가지 방식을 취해 만들 수 있다.

// 1. Edge List
const graph = [[0, 2], [2, 3], [2, 1], [1, 3]];
// connection을 보여주고 있는 배열들이다. 각 노드들 간의 연결관계
// 0은 2와(또는 반대), 2는 3과, 2는 1과, 1은 3과 연결되어 있다는 의미이다.

// 2. Adjacent List
const graph2 = [[2], [2, 3], [0, 1, 3], [1, 2]];
// index는 Node를 가리키고, value는 Node의 Neighbor를 가리키는 형태
// 0번째 index의 노드는 2와 이웃, 1번째 index의 노드는 2, 3과 이웃,
// 2번째 index의 노드는 0, 1, 3과 이웃, 3번째 index의 노드는 1, 2와 이웃
// 배열 말고 Hash Table 또는 Linked List로 만들 수도 있다.

// 3-1. Adjacent Matrix
const graph3 = [
  [0, 0, 1, 0], // 0번째 index는 2번째 index 와 연결
  [0, 0, 1, 1], // Node 1은 Node 2, 3과 연결
  [1, 1, 0, 1], // Node 2는 Node 0, 1, 3과 연결
  [0, 1, 1, 0] // Node 3은 Node 1, 2와 연결
]

// 3-2. Adjacent Matrix
const graph4 = {
  0: [0, 0, 1, 0], // 0번째 index는 2번째 index 와 연결
  1: [0, 0, 1, 1], // Node 1은 Node 2, 3과 연결
  2: [1, 1, 0, 1], // Node 2는 Node 0, 1, 3과 연결
  3: [0, 1, 1, 0] // Node 3은 Node 1, 2와 연결
}
// graph3과 graph4는 동일한 표현방식이다. 배열로 표현했느냐, 객체로 표현했느냐의 차이일 뿐이다.

 

# Graphs method Implementation

class Graph { 
  constructor() { 
    this.numberOfNodes = 0;
    this.adjacentList = {
    }; 
  } 
  addVertex(node)  { 
  } 
  addEdge(node1, node2) { 
    //undirected Graph 
  } 
  showConnections() { 
    const allNodes = Object.keys(this.adjacentList); 
    for (let node of allNodes) { 
      let nodeConnections = this.adjacentList[node]; 
      let connections = ""; 
      let vertex;
      for (vertex of nodeConnections) {
        connections += vertex + " ";
      } 
      console.log(node + "-->" + connections); 
    } 
} 
} 

const myGraph = new Graph();
myGraph.addVertex('0');
myGraph.addVertex('1');
myGraph.addVertex('2');
myGraph.addVertex('3');
myGraph.addVertex('4');
myGraph.addVertex('5');
myGraph.addVertex('6');
myGraph.addEdge('3', '1'); 
myGraph.addEdge('3', '4'); 
myGraph.addEdge('4', '2'); 
myGraph.addEdge('4', '5'); 
myGraph.addEdge('1', '2'); 
myGraph.addEdge('1', '0'); 
myGraph.addEdge('0', '2'); 
myGraph.addEdge('6', '5');

myGraph.showConnections(); 
//Answer:
// 0-->1 2 
// 1-->3 2 0 
// 2-->4 1 0 
// 3-->1 4 
// 4-->3 2 5 
// 5-->4 6 
// 6-->5

 

3. Graphs 결론

- 장점 : 데이터 간의 관계성

- 단점 : Scaling is Hard

이러한 단점을 상쇄시키기 위해 주로 neo4j 같은 것을 이용해서 만든다고 한다.