알고리즘 - DFS, BFS (JS 구현)

DFS와 BFS 모두 그래프를 탐색하는 방법중 하나입니다.

---

1. DFS(Depth-First-Search) 란?

루트 노드에서 시작해서 한 분기를 모두 방문하고 다음 분기로 넘어가는 방식입니다.

인접 노드를 깊이 우선으로  탐색하기 때문에 깊이 우선 탐색, DFS 라고 불립니다.

 

DFS의 예로 미로 찾기를 들 수 있습니다.

(최대한 한 방향으로 이동하고,

막다른 길에서는 이전 갈림길로 되돌아와

다시 한 방향으로 이동하기를 반복함)

 

위 예제 그래프를 DFS로 탐색하면

방문한 노드 순서는 1-2-4-5-3-6-7 입니다.

---

2. BFS(Breadth-First-Search) 란?

루트 노드에서 시작해서 인접한 노드들을 먼저 모두 탐색 하는 방식입니다.

인접 노드를 너비를 우선으로  탐색하기 때문에 너비 우선 탐색, BFS라고 불립니다.

위 예제 그래프를 BFS로 탐색하면

방문한 노드 순서는 1-2-3-4-5-6 입니다.

---

3. DFS, BFS 구현하기

 

DFS는 stack or 재귀함수 

BFS는 queue로 구현 가능합니다.

 

 

1. Node 클래스

class Node {
  constructor(data) {
    this.data = data;
    this.adjacencyList = [];
    this.visited = false;
  }
}

 

2. Graph 클래스

class Graph {
  nodes = null;
  constructor(size) {
    this.nodes = new Array(size);
    for (let i = 0; i < size; i++) {
      this.nodes[i] = new Node(i);
    }
  }
  addEdge(idx1, idx2) { // 노드의 인접 관계 생성 메서드
    let node1 = this.nodes[idx1];
    let node2 = this.nodes[idx2];

    if (!node1.adjacencyList.includes(node2)) {
      node1.adjacencyList.push(node2);
    }
    if (!node2.adjacencyList.includes(node1)) {
      node2.adjacencyList.push(node1);
    }
  }

  dfs(idx) {
    let root = this.nodes[idx]; //idx를 받아 nodes 배열에서 루트노드를 정함
    let stack = []; // 스택 생성
    stack.push(root); // 스택에 루트 노드 푸시
    root.visited = true; // 루트 노드 스택에 들어갔으니 방문 체크

    while (stack.length !== 0) { // 스택이 비어있을 때 까지
      let popedNode = stack.pop(); // 스택에서 노드 하나 꺼냄

      for (let adjacencyNode of popedNode.adjacencyList) { // 꺼낸 노드의 인접 노드들
        if (adjacencyNode.visited === false) { // 인접노드에 방문 안했으면
          adjacencyNode.visited = true; // 방문처리
          stack.push(adjacencyNode); // 스택에 해당 인접노드 푸시
        } // 스택에는 루트의 인접노드들이 쌓이고 인접노드들이 또 쌓이고 반복하다가
      } //  인접노드가 없으면 반복문이 종료되고 종료 되고 종료되고 반복하다가
      this.visit(popedNode);
    } //  stack의 모든 노드들을 방문하면 dfs 함수 최종 종료
  }

  bfs(idx) {
    let root = this.nodes[idx];
    let queue = []; // 큐 생성
    queue.push(root); // 큐에 루트 노드 푸시
    root.visited = true; // 방문 처리
					// 이하 dfs스택과 설명 동일
 
    while (queue.length !== 0) {
      let deQueuedNode = queue.shift();

      for (let adjacencyNode of deQueuedNode.adjacencyList) {
        if (adjacencyNode.visited === false) {
          deQueuedNode.visited = true;
          queue.push(adjacencyNode);
        }
      }
      this.visit(deQueuedNode);
    }
  }

  visit(node) {
    console.log(`방문한 노드 데이터: ${node.data}`);
  }
}

 

 

3. 직접 구현한 함수 실행 결과

구현한 그래프 형태

DFS 결과는 다음과 같습니다.

 

BFS 결과는 다음과 같습니다.