그래프 알고리즘 구현과 간단한 순회 알고리즘 (javascript)

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

  /**
   * @param {string} vertex
   */
  addVertex(vertex) {
    if ( this.hasThisVertex(vertex) ) return;
    this.adjacencyList[vertex] = [];
  };

  removeVertex(vertex) {
    if (this.hasThisVertex(vertex)) {
      // 1) vertex 리스트 삭제
      delete this.adjacencyList[vertex];

      // 2) 이 vertext에 연결하고 있는 노드들의 리스트에서 원소 삭제
      for (let key in this.adjacencyList) this.removeEdge(key, vertex);
    }
  };

  /**
   * "Not Directed" Graph
   * @param {String} startVtx 
   * @param {String} endVtx 
   * @returns void
   */
  addEdge(startVtx, endVtx) {
    if (this.hasTheseVertexes(startVtx, endVtx) === false) return; 
    if (this.areTheseVetexesConnected(startVtx, endVtx)) return;

    // Now Connect
    this.adjacencyList[startVtx].push(endVtx);
    this.adjacencyList[endVtx].push(startVtx);
  };

  removeEdge(startVtx, endVtx) {
    this.adjacencyList[startVtx] = this.adjacencyList[startVtx].filter(v => v !== endVtx);
  }

  /**
   * check if all vertexed exist in this graph.
   * @param  {...any} vertexes 
   * @returns true only if all vertexes exits.
   */
  hasTheseVertexes(...vertexes) {
    for (let v of vertexes) {
      if (this.adjacencyList[v]) continue
      else return false;
    }
    return true;
  };

  hasThisVertex(vertex) {
    if (this.adjacencyList[vertex]) 
      return true;
    else 
      return false;
  }

  areTheseVetexesConnected(startVtx, endVtx) {
    const startVtxList = this.adjacencyList[startVtx];
    const startVtxHasEndVtx = startVtxList.includes(endVtx);

    const endVtxList = this.adjacencyList[endVtx];
    const endVtxHasStartVtx = endVtxList.includes(startVtx);

    if (startVtxHasEndVtx && endVtxHasStartVtx) 
      return true;
    else
      return false;
  }

  DFS(startVtx, callBack) {
    // 1) 방문 여부 문서(객체) 만들기
    const visitDocument = {};
    const keys = Object.keys(this.adjacencyList);
    for (let key of keys) visitDocument[key] = false;

    // 2) 스택 만들기
    const stack = new Stack();

    // 3) 재귀함수 호출
    this.recursiveDFS(startVtx, stack, visitDocument, callBack);

    // 4) 종료
    console.log('dfs 종료');
  }

  BFS(startVtx, callBack) {
     // 1) 방문 여부 문서(객체) 만들기
     const visitDocument = {};
     const keys = Object.keys(this.adjacencyList);
     for (let key of keys) visitDocument[key] = false;
 
     // 2) 큐 만들기
     const queue = new Queue();
 
     // 3) 재귀함수 호출
     this.recursiveBFS(startVtx, queue, visitDocument, callBack);
 
     // 4) 종료
     console.log('bfs 종료');
  }

  recursiveDFS(vertex, stack, visitDocument, callBack) {
    // 1) 해당 vertex의 방문 체크
    visitDocument[vertex] = true;

    // 방문한 노드에 어떤 처리
    callBack(vertex);

    // 2) 다음 자식 노드들 모두 스택에 넣기
    const nextNodes = this.getConnectedNodes(vertex);
    for (let node of nextNodes) {
      stack.push(node);
    }
    
    // 3) 스택에서 vertex 하나 가져오기 -> 방문했는지 확인
    while ( !stack.isEmpty() ) {
      const nextNode = stack.pop();
      const isVisitedNode = visitDocument[nextNode];
      if (isVisitedNode === false) {
        this.recursiveDFS(nextNode, stack, visitDocument, callBack);
      }
    }
    
    return;
  }

  recursiveBFS(vertex, queue, visitDocument, callBack) {
    // 1) 해당 vertex의 방문 체크
    visitDocument[vertex] = true;

    // 방문한 노드에 어떤 처리
    callBack(vertex);

    // 2) 다음 자식 노드들 모두 큐에 넣기
    const nextNodes = this.getConnectedNodes(vertex);
    for (let node of nextNodes) {
      queue.enqueue(node);
    }
    
    // 3) 큐에서 vertex 하나 가져오기 -> 방문했는지 확인
    while ( !queue.isEmpty() ) {
      const nextNode = queue.dequeue();
      const isVisitedNode = visitDocument[nextNode];
      if (isVisitedNode === false) {
        this.recursiveBFS(nextNode, queue, visitDocument, callBack);
      }
    }
    
    return;
  }

  getConnectedNodes(vertex) {
    return this.adjacencyList[vertex];
  }

}

자바스크립트로는 처음 그래프를 간단히 구현해봤는데, 중복되는 코드들이 있으나 자바에서 간단히 인터페이스로 처리할 수 있는 것을 자바스크립트에서는 어떻게 해야 할지 다른 사람이 만든 코드를 봐야 하겠다.

 

그나저나, 옛날에는 그래프 하면 뭔가 구현하기 힘든 구조였는데, 지금 와서는 아주 어렵진 않은듯 싶다. 재귀가 익숙해진 것이 득이 된 것 같다. 물론 아주 좋은 코드라고 할 수는 없지만 한 번도 오류를 일으키지 않고 한 번에 작성했다.