DFS와 DFS

DFS와 BFS란? DFS와 BFS는 모두 그래프를 탐색하는 알고리즘이다. 두 탐색은 모든 정점을 한번씩 방문한다는 동일한 목표를 가지고 있지만, 그 과정에서 탐색하는 방식에는 차이가 있다. DFS는 위의 그림과 같이 해당 노드를 기준으로 더 깊은 노드를 우선적으로 탐색하는 방식이다. (스택을 사용하여 구현하지만 스택을 사용하지 않고도 구현 가능하다는 특징을 가짐, 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문) BFS는 너비를 우선적으로 탐색하는 방식이다. (최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용함) DFS BFS 인접행렬 혹은 인접리스트로 그래프 구현 인접행렬 혹은 인접리스트로 그래프 구현 스택 혹은 재귀로 구현 큐로 구현 DFS 구현 DFS 또는 BFS를 구현하..
알고리즘/개념 2019. 9. 10. 14:31
1