알고리즘 기초 - DFS/BFS

반응형

- DFS 란?

정의!

깊이 우선 탐색(Depth-First Search), 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동합니다.

 

동작 과정!

DFS에서는 스택을 사용합니다.

1. 시작 노드를 스택에 삽입 하고 방문 처리 해줍니다.

2. 스택의 최상단 노드에 방문하지 않은 이웃 노드가 있다면 그 노드를 스택에 넣어주고 방문처리해줍니다. 그렇지 않으면 스택의 최상단 노드를 꺼내줍니다.

3. 방문하지 않은 노드가 존재하지 않아, 더 이상 수행할 수 없을 때 까지 2번의 과정을 반복 수행해줍니다.

 

아래 그래프로 예를 들어보겠습니다.

위와 같은 그래프가 있을 때, 탐색 순서는 1-2-7-6-8-3-4-5입니다. DFS는 단순 재귀함수를 이용해 많이 구현합니다.

def dfs(graph, v, visited):
    visited[v] = True
    print(v)
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

 

 

- DFS 란?

정의!

너비 우선 탐색(Breadth-First Search), 가까운 노드부터 탐색하는 알고리즘입니다. 최대한 넓게 이동하고, 더 이상  갈 곳이 없을 경우 아래로 이동합니다.

 

동작 과정!

BFS는 큐를 사용합니다.

1. 시작 노드를 큐에 넣고 방문처리 해줍니다.

2. 큐에서 노드를 꺼내 그 노드의 이웃 노드 중에서 방문하지 않은 노드를 찾아 모두 큐에 넣어주고 방문 처리합니다.

3. 방문하지 않은 노드가 존재하지 않아, 더 이상 수행할 수 없을 때 까지 2번의 과정을 반복 수행해줍니다.

 

DFS에서 사용한 예시 그래프의 경우 BFS를 사용한다면 탐색 순서는 1-2-3-8-7-4-5-6입니다. 그럼 코드로 구현해보겠습니다. 자료구조로는 큐가 사용됩니다.

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v)
        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)