DFS / BFS
📝 간단한 개념정리
- DFS(Depth-First-Search) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
- BFS(Breadth-First-Search) : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘.
| |
DFS |
BFS |
| 동작 원리 |
스택 |
큐 |
| 구현 방법 |
재귀 함수 이용 |
큐 자료구조 이용 |
👆🏻 DFS
# DFS
def dfs(graph, v, visited):
# 현재노드 방문처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
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, 7, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * len(graph)
# 정의된 dfs 함수 호출
dfs(graph, 1, visited)
결과값
1 2 7 8 3 4 5
// DFS
function dfs(graph, v, visited) {
// 현재노드 방문처리
visited[v] = true;
console.log(v);
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
graph[v].forEach(i => {
// 방문한 노드인지 확인
if (visited[i] === false) {
dfs(graph, i, visited);
}
});
}
var graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 7, 8],
[1, 7]
]
var visited = [];
for(var i=0; i < graph.length; i++){
visited.push(false);
}
dfs(graph, 1, visited);
결과값
1
2
7
8
3
4
5
🤘🏻 BFS
# BFS
from collections import deque
def bfs(graph, start, visited):
# 큐 구현을 위해 deque라이브러리 사용
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, 7, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * len(graph)
# 정의된 dfs 함수 호출
bfs(graph, 1, visited)
결과값
1 2 3 8 7 4 5
// BFS
class Queue {
constructor() {
this._arr = [];
}
enqueue(item) {
this._arr.push(item);
}
dequeue() {
return this._arr.shift();
}
}
function bfs(graph, start, visited) {
const queue = new Queue;
queue.enqueue(start);
// 현재노드 방문처리
visited[start] = true;
//console.log(`v : ${v}, visited[${v}] : ${visited[v]}, graph[${v}] : ${graph[v]}`)
// 큐가 빌 때까지 반복
while(queue._arr.length > 0) {
// 큐에서 하나의 원소를 뽑아 출력
var v = queue.dequeue();
console.log(v);
// 해당 원소와 연결된 아직 방문하지 않은 원소들을 큐에 삽입
graph[v].forEach(i => {
if (visited[i] === false) {
queue.enqueue(i);
visited[i] = true;
}
});
}
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
}
var graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 7, 8],
[1, 7]
]
var visited = [];
for(var i=0; i < graph.length; i++){
visited.push(false);
}
bfs(graph, 1, visited);
결과값
1
2
3
8
7
4
5
※ 주의사항
- 큐를 구현할 때 클래스로 구현해서 while(queue)로만 코드를 작성하면 마지막에 undefined가 출력되면서 forEach부분에서 오류가 남 => while(queue._arr.length > 0)으로 수정했음.
🤲🏻 차이점
- Python에서 각 노드가 방문된 정보를 리스트 자료형으로 표현할 때 visited = [False] * len(graph)로 한 줄로 구현가능함. 그 이유는 * 연산자가 존재하기 때문. 하지만 Javascript에서는 불가능. => 빈 배열을 생성 후 for문으로 graph의 길이 만큼 false를 push()함수로 넣어줌.
- Python에서 for ~ in 문을 Javascript에서는 forEach문을 사용함.
- Python에서 boolean은 True, False로 제일 앞 글자는 대문자이지만 Javascript에서는 boolean은 모두 소문자로 이루어져 있음 => true, false
참고자료
작성일자 : 2022년 4월 28일
