BFS vs DFS

DFS : 깊이 우선 탐색, 루트 노드의 한 브런치의 마지막 노드까지, 모든 노드를 탐색한 후 다음 브런치를 탐색하는 방법.

한 방향으로 계속 탐색하다가 마지막 노드에 도달하면 가장 가까운 갈림길로 돌아가 새로운 브런치를 탐색한다.

모든 노드를 방문할 때, 완전 탐색을 할 때 사용한다.

 

재귀적으로 동작하며, 자기 자신을 호출하는 순환 알고리즘의 형태이다.

Stack 자료구조를 사용하여 후입선출(LIFO) 원칙으로 탐색한다.

 

 

 

BFS : 너비 우선 탐색, 루트 노드와 인접한 노드부터 우선적으로 탐색하는 알고리즘

 

최단 경로를 찾을 때 사용한다.

시작점에서 목적지까지 한 단계씩 탐색하기 때문. 목적지에 도달하는 순간 알고리즘을 종료한다. 더 많은 단계를 거쳐야 목적지에 도달할 수 있는 경로는 더 이상 탐색할 필요가 없다.

 

재귀적으로 동작하지 않는다.

Queue 자료구조를 사용하여 선입선출(FIFO) 원칙으로 탐색한다.

 

 

공통점 : 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 이를 생략할 경우 무한루프에 빠질 수 있다.

 

 

시간 복잡도

그래프(정점의 수: N, 간선의 수: E) 조회

인접 행렬로 표현된 그래프 : O(N^2) : 간선의 수 E와는 무관하게 가로 N, 세로 N개의 matrix로 정점 간 연결관계를 표현하기 때문

인접 리스트로 표현된 그래프 : O(N+E) : 모든 정점과 간선을 표현하기 때문

 

 

 

 

- 성능 차이가 발생하는 이유?

 

- 최단거리를 찾을 때에는 어떤 알고리즘을 사용하는지?

 

- 그 이유는?