너비 우선 탐색(BFS)

참고
https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/BFS%20%26%20DFS.md
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

너비 우선 탐색(BFS)

• 루트 정점 혹은 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 알고리즘입니다.
• 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색합니다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있게 큐(Queue)를 사용했습니다.
• 사용예 : 두 노드 간의 최단 경로, 임의의 경로를 찾고 싶을 때

code

// ----------------------- 방향 그래프 코드 -----------------------

function directedGraph() {
  this.edges = {};
}

directedGraph.prototype.addVertex = function(vertex) {
  this.edges[vertex] = {}
}

directedGraph.prototype.addEdge = function(goVertex, stopVertex, weight) {
  if(weight == undefined) {
    weight = 0
  }
  this.edges[goVertex][stopVertex] = weight;
}

directedGraph.prototype.removeEdge = function(goVertex, stopVertex) {
  if(this.edges[goVertex] && this.edges[goVertex][stopVertex] != undefined) {
    delete this.edges[goVertex][stopVertex];
  }
}

directedGraph.prototype.removeVertex = function(vertex) {
  for(var allEdge in this.edges[vertex]) {
    this.removeEdge(allEdge, vertex);
  }
  delete this.edges[vertex]
}






// ----------------------- BFS 탐색 코드 -----------------------

directedGraph.prototype.travelBFS = function(vertex) {
  var queue = [];
  var visited = {};

  queue.push(vertex)

  while(queue.length) {
    vertex = queue.shift();
    if(!visited[vertex]) {
      visited[vertex] = true;
      console.log(vertex, '방문 완료')
      for(var nextVertex in this.edges[vertex]) {
        queue.push(nextVertex);
      }
    }
  }
}




// ----------------------- 방향 그래프 정점,간선 추가 -----------------------
var graph2 = new directedGraph();
graph2.addVertex('A')
graph2.addVertex('B')
graph2.addVertex('C')

graph2.addEdge('A', 'B', 1)
graph2.addEdge('B', 'C', 1)
graph2.addEdge('C', 'A', 1)

console.log(graph2.edges)
// { A: { B: 1 }, B: { C: 1 }, C: { A: 1 } }
// 위의 객체 설명
// A -> B
// B -> C
// C -> A



// ----------------------- BFS A 탐색 -----------------------
graph2.travelBFS('A')
// A 방문 완료
// B 방문 완료
// C 방문 완료

// ----------------------- BFS B 탐색 -----------------------
graph2.travelBFS('B')
// B 방문 완료
// C 방문 완료
// A 방문 완료

// ----------------------- BFS C 탐색 -----------------------
graph2.travelBFS('C')
// C 방문 완료
// A 방문 완료
// B 방문 완료

설명

// ----------------------- BFS 탐색 코드 -----------------------

// (while문)
//  1) 해당 정점 탐색 후 삭제
//  2) 해당 정점의 인접 정점 탐색 준비
//  3) queue.length > 0 일때까지 반복

// 1. queue배열에 해당 정점 추가
// 2. vertex에 해당 정점 저장 후 queue배열에서 해당 정점 삭제
// 3. visited객체에 해당 정점(vertex)이 탐색 됐는지 확인
//    1) 탐색 안했을 경우 => visited객체에 해당 정점값을 true로 바꾸고 인접 정점 탐색 시작 (queue배열에 인접 정점 추가하고 1번으로 돌아가 반복)
//    2) 탐색 했을 경우 => 모든 정점 방문 종료!!!

directedGraph.prototype.travelBFS = function(vertex) {
  var queue = [];
  var visited = {};

  queue.push(vertex)

  while(queue.length) {
    vertex = queue.shift();
    if(!visited[vertex]) {
      visited[vertex] = true;
      console.log(vertex, '방문 완료')
      for(var nextVertex in this.edges[vertex]) {
        queue.push(nextVertex);
      }
    }
  }
}