Computer Science/Algorithm, Data Structure

자바스크립트 자료구조 그래프(Graph)

Write and Remember 2019. 6. 21. 02:44

모든 자바스크립트 개발자가 알아야 하는 33가지 개념

 

그래프(Graph)에 대해 알아보자.

 

그래프는 두 가지로 나눠진다. 

 

방향 그래프(Directed Graph)

 

출처: Wikipedia

 

무방향 그래프(Undirected Graph)

 

위의 사진의 방향성이 없는 그래프를 의미한다.

 

그래프에선 노드를 정점(Vertex)이라고도 하고

 

정점을 이어주는 것을 간선(Edge)이라 한다.

 

차수(Degree)란 하나의 정점에 닿는 간선의 수를 의미하고

 

간선을 한 번만 통해 갈 수 있으면 인접(Adjacent)하다고 한다.  

 

그래프를 인접 리스트(Adjacency List), 인접 행렬(Adjacency Matrix)로 구현 할 수 있다.

 

인접 리스트를 활용하여 간단한 그래프를 구현해보자.

 

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    this.adjacencyList.set(vertex, []);
  }

  addEdge(v, w) {
    this.adjacencyList.get(v).push(w);
    // Undirected graph 구현하려면
    this.adjacencyList.get(w).push(v);
  }
}

const graph = new Graph();

graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("B", "E");
graph.addEdge("C", "E");

console.log(graph); Graph {
  adjacencyList: Map(5) {
    'A' => [ 'B', 'C' ],
    'B' => [ 'A', 'D', 'E' ],
    'C' => [ 'A', 'E' ],
    'D' => [ 'B' ],
    'E' => [ 'B', 'C' ]
  }
}