탐색 알고리즘 DFS / BFS

DFS/BFS는 그래프, 트리 등의 자료구조에서 쓰이는 대표적인 탐색 알고리즘이다.

DFS

DFS는 깊이 우선 탐색 알고리즘이다.

특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가 노드를 방문하고,
다시 돌아가 다른 경로를 탐색하는 알고리즘이다.

동작과정

DFS는 스택 자료구조를 이용하며, 다음과 같이 동작한다.

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS

BFS는 너비 우선 탐색 알고리즘이다.

DFS와 반대로 가까운 노드부터 탐색한다.
BFS는 큐를 사용하여, 인접한 노드를 큐에 넣고, 그것이 먼저 나가게되어, 가까운 노드부터 탐색하게 된다.

동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문처리 한다.
2. 큐에서 노드를 꺼내, 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 삽입하고 방문처리 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

구현

그래프 (인접 리스트)

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

DFS

#python

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

//javascript

function dfs(graph,v,visited) {
    visited.push(v);

    for(let i of graph[v]) {
        if(!visited.includes(i)) {
            dfs(graph,i,visited);
        }
    }
}

let visited = [];
dfs(graph, 1, visited);
console.log(visited) // [1,2,7,6,8,3,4,5]

---

BFS

#python

from collections import deque
def bfs(graph, first, visited):
    queue = deque([first])
    visited[first] = True
    
    while queue:
        v = queue.popleft()
        print(v,end=' ')
        
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


visited = [False]*9
bfs(graph,1,visited)
# 1 2 3 8 7 4 5 6

//javascript

function bfs(graph, first, visited) {
    const queue = [first];
    visited.push(first);

    while(queue.length > 0) {
        const v = queue.shift();
        for(let i of graph[v]) {
            if(!visited.includes(i)) {
                queue.push(i);
                visited.push(i);
            }
        }
    }
}

let visited = [];
bfs(graph,1,visited);
console.log(visited); // 1 2 3 8 7 4 5 6