자바스크립트로 그래프 구현하기

1. 그래프(Stack)

그래프와 그래프 메서드

그래프란?, 그래프 탐색 참조
가중치 방향 그래프(weighted directed graph)는 네 가지 main operations을 수행합니다:

• addNode 노드 삽입
• removeNode 노드 삭제
• addEdge 두 노드 사이에 weighted edge 삽입, 무향 그래프인 경우 양방향 추가
• removeEdge 두 노드 사이의 weighted edge 삭제, 무향 그래프인 경우 양방향 추가

자바스크립트로 그래프 구현하기

class Node {
  constructor(id) {
    this.id = id;
    this.neighbors = []; // 인접 리스트
  }

  addNeighbor(node, weight = 1) {
    this.neighbors.push({ node, weight });
  }

  removeNeighbor(node) {
    const index = this.neighbors.findIndex(({n}) => n === node);
    if (index !== -1) {
      this.neighbors.splice(index, 1);
    }
  }

  getNeighbors() {
    return this.neighbors.map(({node}) => node);
  }

  getWeight(node) {
    const target = this.neighbors.find(({n}) => n === node);
    return target ? target.weight : undefined;
  }
}


class Graph {
  constructor() {
    this.nodes = [];
    this.directed = false; // 기본값은 무향 그래프
  }

  addNode(node) {
    this.nodes.push(node);
  }

  removeNode(node) {
    const index = this.nodes.indexOf(node);
    if (index !== -1) {
      this.nodes.splice(index, 1);
      this.nodes.forEach(n => {
        n.removeNeighbor(node);
      });
    }
  }

  addEdge(node1, node2, weight = 1) {
    node1.addNeighbor(node2, weight);
    if (!this.directed) { // 무향 그래프인 경우에만 양방향 추가
      node2.addNeighbor(node1, weight);
    }
  }

  removeEdge(node1, node2) {
    node1.removeNeighbor(node2);
    if (!this.directed) { // 무향 그래프인 경우에만 양방향 제거
      node2.removeNeighbor(node1);
    }
  }
}

Graph performance

Node

• addNeighbor: O(1)
• removeNeighbor: O(n) (n은 이웃 노드의 개수)
• getNeighbors: O(n) (n은 이웃 노드의 개수)
• getWeight: O(n) (n은 이웃 노드의 개수)
• space complexity: O(k) (k는 노드 객체 하나의 크기(id, neighbors))

Graph

• addNode: O(1)
• removeNode: O(n^2) (n은 노드의 개수)
• addEdge: O(1)
• removeEdge: O(n) (n은 노드의 개수)
• space complexity: O(n) (n은 노드의 개수)

자바스크립트로 DFS 구현하기

function dfs(node, visited = new Set()) {
  console.log(node.id);
  visited.add(node);
  node.neighbors.forEach(({node}) => {
    if (!visited.has(node)) {
      dfs(node, visited);
    }
  });
}

Time complexity

• Best-case: O(1)
• Worst-case: O(V^2)
• Average time: O(V+E)

Space complexity

• Best case: O(V)
• Worst case: O(V)
• Average case: O(V)

자바스크립트로 BFS 구현하기

function bfs(node) {
  const queue = [node];
  const visited = new Set();
  visited.add(node);

  while (queue.length > 0) {
    const current = queue.shift();
    console.log(current.id);
    current.neighbors.forEach(({node}) => {
      if (!visited.has(node)) {
        visited.add(node);
        queue.push(node);
      }
    });
  }
}

Time complexity

• Best-case: O(1)
• Worst-case: O(V^2)
• Average: O(V+E)

Space complexity

• Best case: O(V)
• Worst case: O(V)
• Average case: O(V)

Feedback

• 다음으로 구현한 추상 자료형들의 performance를 분석하자.
• 알고리즘 문제를 풀 때 모르는 자바스크립트 내장 메서드가 많아서 어려움을 느낀다.