[JS] 너비 우선 탐색(BFS)

1. 너비 우선 탐색

 너비 우선 탐색은 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법이다. 깊이 우선 탐색과 반대의 움직임을 보인다고 생각하면 된다. 깊이 우선 탐색이 세로 본능이라면 너비 우선 탐색은 가로본능이라고 생각하면 된다.

 

[그림 1] 깊이 우선 탐색과 너비 우선 탐색의 움직임 

 

 정확히는 거리로 보면 된다. A에서 1떨어진 노드는 B, C 다. 고로 B와 C는 형제다. 하지만 B, C와 A는 부모-자식 관계다. 깊이 우선 탐색은 자식부터 탐색을 하는 구조다. 하지만 너비 우선 탐색은 주변 인접노드, 형제를 먼저 탐색하는 구조다. 너비 우선 탐색은 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입 선출의 구조를 갖는 큐 자료구조를 사용한다. 

 

 

2. 동작 순서

 다음 예를 들어서 너비 우선 탐색에 대한 동작이 어떤 순서로 이루어지는지 설명해보도록 하겠다. 먼저 A를 탐색 후, 방문 처리를 해준 후 큐 자료구조에 A노드를 삽입한다.

 

[그림 2]

 

 큐 자료구조에서 A를 꺼내자. 노드 A와 인접한 노드는 B, C이다. 오름차순 대로 B, C를 탐색한다. 노드 B, C에 대해서는 탐색했다는 것을 표시하기 위해 방문처리를 꼭 해주도록 하자. 그리고 B, C를 큐 자료구조에 넣도록 하자. 

 

[그림 3]

 

 큐 자료구조는 선입 선출 구조이다. 따라서 자료를 꺼낼 때 먼저 들어온 B를 꺼내줘야한다. 노드 B를 큐에서 꺼내서 인접노드를 있는지 본다. B의 인접노드는 A, D, E이다. 하지만 A는 이미 방문 처리를 한 상태다. 그러나 D, E는 아직 방문처리를 하지 않았다. 따라서 오름차순대로 D, E를 탐색해서 방문처리를 한 후 큐 자료구조에 넣도록 하자.

 

[그림 4]

 

 큐에 데이터들을 하나씩 꺼내서 탐색하지 않은 인접 노드가 있는지 검사하는 작업을 한다. 하지만 C, D, E의 인접노드 모두 탐색을 완료한 상태다. 따라서 더 이상 처리할 작업이 없다. 그리고 C, D, E를 다 꺼냈을 땐 큐는 비어있는 상태가 된다. 따라서 너비 우선 탐색 과정은 완전히 끝나게 된다.

 

 

3. 프로그램 코드

const Node = function(data){
  this.data = data; 
  this.link = null;
  this.visited = false;
}

const Graph = function(size){
  this.graph = Array.from({length:size}, (e,i) => new Node(String.fromCharCode(65+i)));

  Graph.prototype.insertEdge = function(v1, v2) {
    const v1Idx = v1.charCodeAt(0)-65;
    const v2Idx = v2.charCodeAt(0)-65;
    let v1Node = this.graph[v1Idx]; 
    let v2Node = this.graph[v2Idx];
    
    if(v1 === v2)
      return;
    if(v1Idx > size || v2Idx > size)
      return;

    while(v1Node.link !== null){
      v1Node = v1Node.link;
    }

    while(v2Node.link !== null){
      v2Node = v2Node.link;
    }

    v1Node.link = new Node(v2);
    v2Node.link = new Node(v1);
  }

  Graph.prototype.printAdjList = function(){
    const adjList = this.graph;
    for(let i=0; i<size; i++){
      let adj = adjList[i];
      let str = adj.data;
      
      while(adj.link !== null){
        adj = adj.link;
        str += adj.data;
      }

      console.log(str.split("").join(" - "));
    }  
  }

  Graph.prototype.BFS = function(){
    const graph = this.graph;
    const q = [];
    let node = graph[0];
    let idx = node.data.charCodeAt(0)-65;
    let str = graph[idx].data;
    graph[idx].visited = true;
    q.push(node);
    
    while(q.length){
      node = q.shift();
      while(node.link !== null){
        node = node.link;
        idx = node.data.charCodeAt(0)-65;
        if(!graph[idx].visited){
          graph[idx].visited = true;
          str += graph[idx].data;
          q.push(graph[idx]);
        }
      }
    }

    console.log(str.split("").join(" → "));
  }
}


const main = (function(){
  const graph = new Graph(5);
  graph.insertEdge('A', 'B');
  graph.insertEdge('A', 'C');
  graph.insertEdge('B', 'D');
  graph.insertEdge('B', 'E');
  graph.insertEdge('C', 'E');

  console.log("The adjList print");
  graph.printAdjList();

  console.log("\n\nBFS print");
  graph.BFS();
}());

 

 

4. 참고 자료

 자바로 배우는 쉬운 자료구조, 한빛 아카데미