BFS / DFS 이해하기

jkpark104·2021년 10월 10일

Algorithms

1. BFS / DFS

트리 또는 그래프 자료구조를 탐색하기 위한 알고리즘

(1) BFS(Breadth-First Search) - 너비 우선 탐색

(트리) 루트 노드를 시작으로 현재 Depth의 노드를 모두 탐색하고 다음 Depth로 이동하며 탐색한다.
(그래프) 한 점(Vertex)에서 가능한 인접 점(Vertex)을 모두 탐색한 후 이동한다.

너비 우선 탐색 (BFS)

(2) DFS(Depth-First Search) - 깊이 우선 탐색

(트리) 루트 노드를 시작으로 브랜치를 따라 가능한 한 멀리 이동하며 탐색한다.
(그래프) 한 점(Vertex)에서 인접 점(Vertex)으로 가능한 한 멀리 이동하며 탐색한다.

깊이 우선 탐색 (DFS)

2. BFS / DFS 알고리즘

(1) BFS

JavaScript를 통한 BFS 알고리즘 구현하기

1번 정점(vertex) 부터 탐색을 시작한다.

BFS 그래프

정점의 개수, 시작 점(vertex), 간선 정보 입력하기

const vertexNumber = 5; // 정점의 개수
const startVertex = 1; // 탐색을 시작할 정점

// 간선 정보
// [ [ 5, 4 ], [ 5, 2 ], [ 1, 2 ], [ 3, 4 ], [ 3, 1 ] ]
const edge = [
  [5, 4],
  [5, 2],
  [1, 2],
  [3, 4],
  [3, 1]
];

1.의 정보를 바탕으로 그래프를 정의하고,
정점의 방문 여부를 저장하는 배열을 생성한다.

// (1) 그래프 정보를 나타내는 배열
// (2) 인접 리스트 형식
const graph = Array.from({ length: vertexNumber + 1 }, () => new Array(0));

// 해당 정점의 방문 여부를 저장하는 배열
const visited = Array.from({ length: vertexNumber + 1 }, () => false);

// 간선 정보를 바탕으로 그래프를 정의함
// [ [], [ 2, 3 ], [ 5, 1 ], [ 4, 1 ], [ 5, 3 ], [ 4, 2 ] ]
for (const [vertex, other] of edge) {
  graph[vertex].push(other);
  graph[other].push(vertex);
}

그래프

각 배열의 요소는 정점의 간선 정보를 나타낸다.
1번 요소의 [2, 3]은 1번 정점이 2번 3번 정점과 이어져 있음을 의미한다.

정점의 방문 여부를 저장하는 배열(visited)

visited 배열의 상태는 해당 정점을 방문하면 false → true로 변경된다.

queue 배열을 이용해 그래프를 탐색한다.
queue에는 해당 정점의 방문하지 않은 인접 정점을 추가한다.

function bfs(start) {
  const queue = [start];
  visited[start] = true;

  while (queue.length) {
    const now = queue.shift();
    console.log(now);

    for (const next of graph[now]) {
      if (visited[next] === false) {
        visited[next] = true;
        queue.push(next);
      }
    }
  }
}

queue

1번 정점을 탐색하면서 queue에는 1번 정점의 인접 정점인 2번 3번 정점이 저장된다.
2번 정점을 탐색하면서 queue에는 2번 정점의 인접 정점인 5번 정점이 저장된다.
3번 정점을 탐색하면서 queue에는 3번 정점의 인접 정점인 4번 정점이 저장된다.
5번 정점을 탐색한다.
4번 정점을 탐색한다.

visited

visited 배열의 상태는 해당 정점의 방문 순서대로 true로 변경된다.

BFS의 결과로 정점은 1 → 2 → 3 → 5 → 4의 순서로 탐색된다.

bfs(startVertex); // 1 2 3 5 4

(2) DFS

JavaScript를 통한 DFS 알고리즘 구현하기

3번 정점(vertex) 부터 탐색을 시작한다.

DFS 그래프

정점의 개수, 시작 점(vertex), 간선 정보 입력하기

const vertexNumber = 5; // 정점의 개수
const startVertex = 3; // 탐색을 시작할 정점

// 간선 정보
// [ [ 5, 4 ], [ 5, 2 ], [ 1, 2 ], [ 3, 4 ], [ 3, 1 ] ]
const edge = [
  [5, 4],
  [5, 2],
  [1, 2],
  [3, 4],
  [3, 1]
];

1.의 정보를 바탕으로 그래프를 정의하고,
정점의 방문 여부를 저장하는 배열을 생성한다.

// (1) 그래프 정보를 나타내는 배열
// (2) 인접 리스트 형식
const graph = Array.from({ length: vertexNumber + 1 }, () => new Array(0));

// 해당 정점의 방문 여부를 저장하는 배열
const visited = Array.from({ length: vertexNumber + 1 }, () => false);

// 간선 정보를 바탕으로 그래프를 정의함
// [ [], [ 2, 3 ], [ 5, 1 ], [ 4, 1 ], [ 5, 3 ], [ 4, 2 ] ]
for (const [vertex, other] of edge) {
  graph[vertex].push(other);
  graph[other].push(vertex);
}

그래프

각 배열의 요소는 정점의 간선 정보를 나타낸다.
1번 요소의 [2, 3]은 1번 정점이 2번 3번 정점과 이어져 있음을 의미한다.

정점의 방문 여부를 저장하는 배열(visited)

visited 배열의 상태는 해당 정점을 방문하면 false → true로 변경된다.

재귀 함수를 통해 DFS를 구현할 수 있다.
DFS는 인접 정점을 따라 가능한 한 깊이 이동하며 그래프를 탐색한다.

function dfs(now) {
  visited[now] = true;
  console.log(now);

  for (const next of graph[now]) {
    if (visited[next] === false) {
      visited[next] = true;
      dfs(next);
    }
  }
}

3번 정점을 탐색하면서 재귀 함수 dfs를 통해 인접 4번 정점으로 이동한다.
4번 정점을 탐색하면서 재귀 함수 dfs를 통해 인접 5번 정점으로 이동한다.
5번 정점을 탐색하면서 재귀 함수 dfs를 통해 인접 2번 정점으로 이동한다.
2번 정점을 탐색하면서 재귀 함수 dfs를 통해 인접 1번 정점으로 이동한다.
1번 정점을 끝으로 모든 정점을 탐색한 dfs는 종료된다.