[Python, JS] DFS/BFS 알고리즘

홍건우·2021년 3월 2일

그래프의 구조

DFS/BFS 알고리즘을 공부하기 위해 먼저 그래프의 기본 구조를 알아야 하므로 짧게나마 공부해보도록 하자.
그래프 그림
그래프는 위의 그림과 같이 노드(Node)와 간선(Edge)으로 표현된다.
두 노드가 간선으로 연결되어 있으면 두 노드는 인접(Adjacent)하다 라고 말한다.
그래프는 크게 2가지 방식으로 표현이 가능하다.

인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현
인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현

	0	1	2
0	0	6	2
1	6	0	무한
2	2	무한	0

6과 2는 노드 사이의 거리라고 생각하도록하자.
연결이 되어 있지 않은 노드끼리는 무한이라고 표현한다.
실제 코드를 작성할때는 무한을 999999999의 정수로 표현할 수 있도록 하자.

# 인접 행렬 방식
INF = 999999999

graph = [
    [0, 6, 2]
    [6, 0 , INF]
    [2, INF, 0]
]

print(graph)
# [[0, 6, 2], [6, 0, 999999999], [2, 999999999, 0]]

# 인접 리스트 방식
graph = [[] for _ in range(3)]]
graph[0].append((1, 6))
graph[0].append((2, 2))
graph[1].append((0, 6))
graph[2].append((0, 2))

print(graph)
# [[(1, 6), (2, 2)], [(0, 6)], [(0, 2)]]

메모리 측면에서 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 많이 필요하게 된다. 인접 리스트 방식은 연결된 정보만 저장하기 때문에 메모리를 적게 사용할 수 있다. 이런 특성 때문에 속도의 측면에서 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
예를 들어 노드1과 노드 2가 연결되어 있는지 확인하기 위해 인접 행렬 방식은 graph[1][2]로 간단하게 알 수 있다. 하지만 인접 리스트 방식은 앞에서부터 차례대로 확인해야 한다.

DFS(Depth-First Search)

DFS는 깊이 우선 탐색이라고도 부른다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
이 알고리즘은 단순하게 가장 깊숙이 위치하는 노드에 닿을 때까지 탐색하면 된다.
아래의 그림은 위키에서 가져온 예시이다.

DFS 예제

Python

# DFS
def dfs(graph, v, visited):
    # 현재노드 방문 처리
    visited[v] = True
    print(v, end = ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]: # visited[i]가 False일때 실행
            dfs(graph, i, visited)

graph = [
    [],
    [2, 5, 9],
    [1, 3],
    [2, 4],
    [3],
    [1, 6, 8],
    [5, 7],
    [6],
    [5],
    [1, 10],
    [9]
]

visited = [False] * 11

dfs(graph, 1, visited)

# 결과값 : 1 2 3 4 5 6 7 8 9 10

JavaScript

function dfs(graph, v, visitied) {
  visitied[v] = true;
  console.log(v);

  for(i of graph[v]) {
    if (!visitied[i]) {
      dfs(graph, i, visitied);
    }
  }
}

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visitied = Array.from({length: 9}, () => false);

dfs(graph, 1, visitied);

DFS는 스택을 이용하는 알고리즘이기 때문에 재귀 함수를 이용하여 간결하게 구현할 수 있다.

BFS(Breadth First Search)

BFS는 너비 우선 탐색이라고도 부른다. 가까운 노드부터 탐색하는 알고리즘 이다.
BFS는 선입선출 방식인 큐 자료구조를 이용하여 구현한다.
인접한 노드를 반복적으로 큐에 넣도록 하면 큐의 선입선출에 의해 먼저 들어온 것이 먼저 나가게 된다.
아래의 그림은 위키에서 가져온 예시이다.
BFS 예시
아래의 그래프를 코드로 구현하면 다음과 같다.
BFS 코드 예시

Python

from collections import deque # 큐(Queue) 구현을 위해 deque 라이브러리 사용

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True # 현재 노드를 방문 처리
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

#결과값 : 1 2 3 8 7 4 5 6

JavaScript

function bfs(graph, start, visitied) {
  let queue = [start];
  visitied[start] = true;
  while (queue.length) {
    v = queue.shift();
    console.log(v);
    for(i of graph[v]) {
      if (!visitied[i]) {
        queue.push(i)
        visitied[i] = true;
      }
    }
  }
}

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visitied = Array.from({length: 9}, () => false);

bfs(graph, 1, visitied);