본문 바로가기
Computer Science/Algorithm, Data Structure

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

by Write and Remember 2019. 6. 21.

모든 자바스크립트 개발자가 알아야 하는 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(vertex, w) {
    this.AdjacencyList.get(vertex).push(w)
    // Undirected graph 구현하려면
    this.AdjacencyList.get(w).push(vertex)
  }
}

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 {
  AdjList:
   Map {
     'A' => [ 'B', 'C' ],
     'B' => [ 'A', 'D', 'E' ],
     'C' => [ 'A', 'E' ],
     'D' => [ 'B' ],
     'E' => [ 'B', 'C' ] } }
*/     

댓글0