[Algorithm] 알고리즘 BFS, DFS란 무엇인가?

• BFS  vs DFS

DFS와 BFS를 직관적으로 잘 보여주는 그림이다.   

 

1. DFS (Depth First Search) :  깊이 우선 탐색 

말 그래로 그래프 또는 트리에서 깊이를 우선하여 탐색하는 알고리즘이다. 

 

* 주로 사용하는 목적은 모든 노드를 방문하고자 할 때 쓰임 

1-1 순환하는 원리 

DFS 알고리즘은 스택을 이용해 구현할 수 있다.   

1-2 알고리즘 스택의 DFS 과정 

				4
			3	3
		2	2	2
	1	1	1	1
0	0	0	0	0

               첫 번째                              두 번째                              세 번째                            네 번째                           다섯 번째  

3
2	2
1	1	1
0	0	0	0

            여섯 번째                          일곱 번째                           여덟 번째                           열 번째                           열한 번째

 

하나씩 벽돌을 쌓듯이 쌓다가 마지막에 들어온 순서대로 차례로 나가는(Last In First Out, LIFO) 원리로 트리가 순환하게 됩니다. 

 

2. BFS(Breadth First Search)  :  너비 우선 탐색 

트리 또는 그래프에서 너비를 우선하여 탐색하는 알고리즘이다.

 

* 주로 사용하는 목적은 최단 경로 찾기가 대표적임

 

2-1 순환하는 원리 

BFS는 큐를 이용해 구현할 수 있다.

 

위 그림에서 알 수 있듯 BFS는 먼저 들어온 값이 먼저 나가는(First In First Out, FIFO) 큐와 같은 원리로 트리가 순환하게 됩니다.

References

dawoonjeong.com/algorithm-graph-bfs-dfs/

[Algorithm] 그래프 순회(Graph Traversal) - BFS, DFS

velog.io/@sohi_5/algorithmDFS

[자료구조와 알고리즘] DFS (깊이 우선 탐색)

gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog