ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 자바스크립트 자료구조 그래프(Graph)
    Computer Science/Algorithm, Data Structure 2019.06.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(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