BFS

BFS

너비우선탐색으로 루트 노드로 부터 인접 노드를 탐색한다.

• 기본적으로 그래프에서의 결과 대상을 탐색하는데 이용한다.

BFS 코드

const bfs = (graph, startNode) => {
    let visited = []; // 탐색을 마친 노드들
    let needVisit = []; // 탐색해야할 노드들

    needVisit.push(startNode); // 노드 탐색 시작

    while (needVisit.length !== 0) {
      // 탐색해야할 노드가 남아있다면
      const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
      if (!visited.includes(node)) {
        // 해당 노드가 탐색된 적 없다면
        visited.push(node);
        needVisit = [...needVisit, ...graph[node]];
      }
      console.log(visited, needVisit, node);
    }
    return visited;
  };

코드분석

매개변수를 통해 받아온 객체 형태(graph)와 startNode값을 통해 시작노드로 부터 탐색을 시작하고 해당 노드가 남아 있지 않을때까지 반복한다.

해당 노드가 탐색된 적 없는 것이라면 이미 graph에서 연결된 내용과 기존에 needVisit의 배열을 합친 needVisit을 만들어낸다.
graph에서 기존에 연결된 내용 (이미 탐색한 노드)는 if문을 통해 걸러낸다.

이를 통해 BFS를 구현 할 수 있다.

그래프에 적용하기

let gr = new Graph();
gr.addNode(1);
gr.addNode(2);
gr.addNode(3);
gr.addNode(4);
gr.addNode(5);
gr.addNode(6);
gr.addNode(7);

gr.addEdge(1, 2);
gr.addEdge(2, 7);
gr.addEdge(6, 7);
gr.addEdge(3, 7);
gr.addEdge(3, 4);
gr.addEdge(4, 5);

console.log(bfs(gr.nodes, 1));

new Graph()부분은 위의 그래프 내용에서 참조하길 바람

bfs를 통해 gr.nodes에 대해 연결된 상태의 그래프를 1번부터 탐색을 진행하면
[ 1, 2, 7, 6, 3, 4, 5 ] 형태로 탐색을 진행한다.
그림으로 그려보면 더 이해가 쉽다.