[자바] 탐색 알고리즘 - DFS, BFS

DFS (깊이 우선 탐색)

그래프 완전 탐색 기법 중 하나. 

그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하고 이의 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행

-> 한 번 방문한 노드를 다시 방문하면 안됨 -> 노드 방문 여부를 체크할 배열이 필

특징

• 재귀함수로 구현 -> stack overflow에 유의!
• 후입선출 -> 스택 자료구조 이용 

=> 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 문제에 이용됨

=> 시간복잡도 = O(V+E) -v: 노드 수, e: 엣지 개수

 

 

BFS (너비 우선 탐색)

그래프 완전 탐색 기법 중 하나. 

그래프의 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

-> 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장

특징

• 선입선출 -> 큐 자료구조 이용 

=> 시간복잡도 = O(V+E) -v: 노드 수, e: 엣지 개수