class Graph {
  constructor() {
    // 정점목록
    this.vertices = [];
    // 인접리스트
    this.adjList = {};
  }

  // 정점 추가
  addVertex(v) {
    this.vertices.push(v);
    this.adjList[v] = [];
  }

  // 간선 추가
  addEdge(v, w) {
    this.adjList[v] ? this.adjList[v].push(w) : (this.adjList[v] = []);
    this.adjList[w] ? this.adjList[w].push(v) : (this.adjList[w] = []);
  }

  // BFS - 반복문 이용
  bfsWithLoop(startV) {
    let queue = [];
    const visiteds = new Set();
    let neighbors = this.adjList[startV] || [];
    let target;
    neighbors.sort();
    queue.push(startV);
    queue = [...queue, ...neighbors];

    const result = [];

    while (queue.length > 0) {
      target = queue.shift();
      result.push(target);
      visiteds.add(target);
      neighbors = this.adjList[target] || [];
      neighbors.sort();
      neighbors.forEach(val => {
        if (!visiteds.has(val) && queue.indexOf(val) < 0) {
          queue.push(val);
        }
      });
    }

    return result;
  }

  // BFS - 재귀 이용
  bfsWithRecursion(startV) {
    return bfs([startV], this.adjList, new Set());

    function bfs(queue, adjList, visiteds) {
      let result = [];

      // base case
      if (queue.length === 0) {
        return result;
      }

      const target = queue.shift();
      result.push(target);
      visiteds.add(target);

      const neighbors = adjList[target] || [];
      neighbors.sort();
      neighbors.forEach(val => {
        if (!visiteds.has(val) && queue.indexOf(val) < 0) {
          queue.push(val);
        }
      });

      return [...result, ...bfs(queue, adjList, visiteds)];
    }
  }
}

// Test
it("bfsWithLoop 메서드는 잘 동작한다.", () => {
  const graph = new Graph();
  const myVertices = [1, 2, 3, 4];
  myVertices.forEach((_, i) => {
    graph.addVertex(myVertices[i]);
  });
  graph.addEdge(1, 2);
  graph.addEdge(1, 3);
  graph.addEdge(1, 4);
  graph.addEdge(2, 4);
  graph.addEdge(3, 4);

  expect(graph.vertices).toEqual([1, 2, 3, 4]);
  expect(graph.adjList).toEqual({
    1: [2, 3, 4],
    2: [1, 4],
    3: [1, 4],
    4: [1, 2, 3],
  });

  expect(graph.bfsWithLoop(1)).toEqual([1, 2, 3, 4]);
});

it("bfsWithRecursion 메서드는 잘 동작한다.", () => {
  const graph = new Graph();
  const myVertices = [1, 2, 3, 4];
  myVertices.forEach((_, i) => {
    graph.addVertex(myVertices[i]);
  });
  graph.addEdge(1, 2);
  graph.addEdge(1, 3);
  graph.addEdge(1, 4);
  graph.addEdge(2, 4);
  graph.addEdge(3, 4);

  expect(graph.vertices).toEqual([1, 2, 3, 4]);
  expect(graph.adjList).toEqual({
    1: [2, 3, 4],
    2: [1, 4],
    3: [1, 4],
    4: [1, 2, 3],
  });

  expect(graph.bfsWithRecursion(1)).toEqual([1, 2, 3, 4]);
});