Javascript의 너비 우선 탐색 순회

BFS는 자식 정점을 방문하기 전에 이웃 정점을 방문하며 검색 프로세스에서 큐가 사용됩니다. 다음은 BFS가 작동하는 방식입니다 -

• 인접한 방문하지 않은 정점을 방문합니다. 방문한 것으로 표시하십시오. 그것을 표시하십시오. 대기열에 삽입하세요.
• 인접한 정점이 없으면 대기열에서 첫 번째 정점을 제거합니다.
• 대기열이 비어 있을 때까지 규칙 1과 규칙 2를 반복합니다.

BFS Traversal이 작동하는 방식에 대한 그림을 살펴보겠습니다.

단계	순회	설명
1		대기열을 초기화합니다.
2		S를 방문하여 시작합니다. (시작 노드)를 방문으로 표시합니다.
3		그러면 S.에서 방문하지 않은 인접 노드가 표시됩니다. 이 예에서는 세 개의 노드가 있지만 알파벳순으로 A,를 선택합니다. 방문한 것으로 표시하고 대기열에 넣습니다.
4		다음으로 S의 방문하지 않은 인접 노드 B . 방문한 것으로 표시하고 대기열에 넣습니다.
5		다음으로 S의 방문하지 않은 인접 노드 C . 방문한 것으로 표시하고 대기열에 넣습니다.
6		지금, S 방문하지 않은 인접 노드가 없습니다. 그래서 우리는 큐에서 빼내고 A를 찾습니다. .
7		에서 A는 D 입니다. 방문하지 않은 인접 노드로. 방문한 것으로 표시하고 대기열에 넣습니다.

이 단계에서는 표시되지 않은(방문하지 않은) 노드가 남지 않습니다. 그러나 알고리즘에 따라 방문하지 않은 모든 노드를 얻기 위해 대기열에서 계속 빼냅니다. 대기열이 비워지면 프로그램이 종료됩니다.

이것을 JavaScript로 구현하는 방법을 살펴보겠습니다.

예시

BFS(node) {
   // Create a Queue and add our initial node in it
   let q = new Queue(this.nodes.length);
   let explored = new Set();
   q.enqueue(node);

   // Mark the first node as explored explored.
   add(node);

   // We'll continue till our queue gets empty
   while (!q.isEmpty()) {
      let t = q.dequeue();

      // Log every element that comes out of the Queue
      console.log(t);

      // 1. In the edges object, we search for nodes this node is directly connected to.
      // 2. We filter out the nodes that have already been explored.
      // 3. Then we mark each unexplored node as explored and add it to the queue.
      this.edges[t]
      .filter(n => !explored.has(n))
      .forEach(n => {
         explored.add(n);
         q.enqueue(n);
      });
   }
}

−

예시

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");

g.BFS("A");

출력

이것은 출력을 줄 것입니다 -

A
C
B
D
G
E
F