그래프탐색은?
- 그래프란 비선형구조로 노드와 간선의 집합
- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는것
- ex) 특정 도시에서 다른 도시로 갈 수 있는지 여부, 특정 단자와 단자가 서로 연결되어 있는지 여부 등
깊이 우선 탐색(DFS, Depth-First Search)
깊이우선탐색(이하 DFS)는 루트노드에서 시작해서 다음 분기로 넘어가기 전에 끝까지 탐색하는 방법이다.
- 스택(Stack)을 사용하며 때로는 재귀호출을 사용한다.
- 너비우선탐색(BFS, Breadth-First Search) 보다 간단하다
- 단순 검색 속도 자체는 BFS비해 느리다.
- 모든 노드를 방문 하고자 하는 경우에 사용
- 알고리즘 구현 시 “노드 방문여부”를 반드시 검사해야한다.
너비 우선 탐색(BFS, Breadth-First Search)
너비우선탐색(이하 BFS)는 루트노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
- 큐(Queue)을 사용한다. (재귀적으로 작동 X)
- DFS보다 좀 더 복잡하다.
- “두 노드 사이의 최단경로”, “임의의 경로”를 찾을때 사용한다.
- 알고리즘 구현 시 “노드 방문여부”를 반드시 검사해야한다.
DFS와 BFS의 차이
참조사이트
https://mygumi.tistory.com/102
https://gmlwjd9405.github.io