[그래프탐색] DFS/BFS

DFS와 BFS를 구현하기 전, Stack과 Queue를 구현할 수 있어야 한다.

 

 

1. Stack 구현

function Stack () {
  this.array = [];
}
 
Stack.prototype.push = function (e) {
  return this.array.push(e)
}
 
Stack.prototype.pop = function () {
  return this.array.pop();
}
 
Stack.prototype.peek = function () {
  return this.array[this.array.length-1];
}
 
Stack.prototype.isEmpty = function () {
  return this.array.length == 0
}
 
var stack = new Stack();
 
stack.push(1);
stack.push(2);
stack.push(3);
 
console.log(stack.pop());
console.log(stack.peek());

 

 

2. Queue 구현

function Queue () {
  this.array = [];
}
 
Queue.prototype.enqueue = function (e) {
  this.array.push(e);
}
 
Queue.prototype.dequeue = function () {
  return this.array.shift();
}
 
Queue.prototype.peek = function (e) {
  return this.array[0];
}
 
Queue.prototype.isEmpty = function () {
  return this.array.length == 0
}
 
var queue = new Queue();
 
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
 
console.log(queue.dequeue());
console.log(queue.peek());

 

 

1. DFS (Depth-First-Search) 구현

 

DFS는 Stack을 이용해 구현할 수 있다. 재귀적으로 푸는 방법또한 있다.

 

우선 키보드 입력을 받는 함수와 그래프를 인접리스트로 표현하는 공통함수는 다음과 같다.

 

백준 1260번 문제를 기반으로 작성하였다.

https://www.acmicpc.net/problem/1260

 

안타깝게도 백준에서는 javascript를 지원하지는 않는다.

 

function connectGraph (S, D, graph) {
  if (graph[S]) {
    graph[S].push(D);
  } else {
    graph[S] = [D];
  }
}
 
function main() {
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });
 
  let N, M, V;
  let graph = {};
 
  let cnt;
 
  rl.on('line', function(line) {
    let input = line.split(" ");
    
    if (input.length > 2) {
      N = input[0], 
      M = input[1], 
      V = input[2];
      cnt = 0;
    }
    else if (input.length == 2) {
      let S = input[0],
      D = input[1];
 
      connectGraph(S, D, graph);
      connectGraph(D, S, graph);
 
      cnt++;
    } else {
      rl.close();
    }
 
    if (cnt >= M) {
      rl.close();
    }
  }).on('close', function() {
    const dfsResult = dfs(graph, V, {}); // dfs
    console.log(dfsResult.join(" ")); // dfs result
    
    const bfsResult = bfs(graph, V, {}); // bfs
    console.log(bfsResult.join(" ")); // bfs result
 
    process.exit();
  });
  
}
 
main();

 

DFS 구현

 

function dfs (graph, start, visit) {
  let stack = new Stack();
  let result = [];
  
  stack.push(start);
 
  while(!stack.isEmpty()) {
    let v = stack.pop();
 
    if (!visit[v]) {
      visit[v] = true;
      result.push(v);
 
      for (let i=0;i<graph[v].length;i++) {
        stack.push(graph[v][i]);
      }
    }
  }
  return result;
}

 

2. BFS (Breadth-First-Search) 구현

 

BFS는 Queue를 활용하여 구현할 수 있다.

 

function bfs (graph, start, visit) {
  let queue = new Queue();
  let result = [];
 
  queue.enqueue(start);
 
  while (!queue.isEmpty()) {
    let enqueued = queue.dequeue();
 
    if (!visit[enqueued]) {
      visit[enqueued] = true;
      result.push(enqueued);
 
      for (let i=0;i<graph[enqueued].length;i++) {
        queue.enqueue(graph[enqueued][i]);
      }
    }
  }
 
  return result;
}