알고리즘 BFS 와 DFS

알고리즘 공부 해봤다면 그래프에서 모든 노드를 탐색하기 위한 기법으로 BFS와 DFS 를 들어봤을 것이다.

 

둘의 공통 목적으로는 다음과 같다.

• 그래프의 탐색의 목적은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이다.
• 그래프의 데이터는 배열처럼 정렬이 되어 있지 않다.
• 그래프에서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.

탐색 방법은 아래 그림과 같다.

모든 노드를 들려야해서 효율이 떨어질순 있지만 이부분은 백트래킹으로 해결이 가능하고 

백트래킹에 대한 내용은 다음포스팅에 이어서 다뤄볼 예정이다.

 

특징

BFS 에 대한 특징

• BFS 는 재귀적으로 동작하지 않는다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
• BFS 는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함
• 즉 선입선출(FIFO) 원칙으로 탐색

 

DFS 에 대한 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 지님
• 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)

시간복잡도

BFS에 대한 시간복잡도는 아래와 같다.

• 인접행렬 : O(V^2)
• 인접리스트 : O(V+E)
  • 참고 : if (check[y]== false) 검사를 하기 때문에 모든 정점을 다 방문하는게 아니라, 간선의 개수 (V)에다가 정점의 개수(E)만큼이 추가되는 것을 의미합니다.

DFS에 대한 시간복잡도는 아래와 같다.

• DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함
  • 인접 리스트로 표현된 그래프 : O(N+E)
  • 인접 행렬로 표현된 그래프 : O(N^2)