[알고리즘] DFS/BFS

그래프를 탐색하는 방법에는 DFS(깊이 우선 탐색) 과 BFS(너비 우선 탐색) 가 있다.

그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

• 그래프 : 정점 (node) 과 그 정점을 연결하는 간선 (edge) 으로 이루어진 자료구조

 

그래프와 트리의 차이

그래프 중에 방향성이 있는 비순환 그래프를 트리라고 한다.

 

DFS 와 BFS  비교

 

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

• 현재 노드에서 갈 수 있는 노드까지 들어가면서 탐색
• 스택 또는 재귀함수로 구현

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

• 현재 노드에서 연결된 가까운 노드부터 탐색
• 큐를 이용하여 구현

 

---

참고

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)