그래프 탐색 알고리즘 - DFS 와 BFS 비교

정의 

• 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을때, 시작점에서 간선(Edge, E)을 타고 이동할 수 있는 정점(Node/Vertex, V)을 모두 찾아야 하는 문제
• 이미 지난 정점은 다시 방문하지 않는다. 

DFS(Depth First Search)

• 그래프에서 한 노드에서 시작해서 모든 노드까지 방문하는 알고리즘 
• 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 
• 깊이가 무한히 깊어지면 스택오버플로우 발생하기에 깊이 제한을 두는 방법으로 처리 가능
• 재귀함수로 짤 경우 Stack 메모리 초과날 수 있기 때문에 주의
• 재귀함수 호출마다 함수와 매개변수를 생성하는 작업이 있기 때문에 시간이 조금 더 걸린다. 

BFS(Breadth FIrst Search) 

• 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 

DFS 와 BFS 차이 

1. 방문 순서 차이

 

2. 구현 자료구조 사용의 차이 

• DFS: Stack 사용하여 탐색 
• BFS: Queue 이용한 탐색

3. DFS는 시작점과 방문한 곳까지 거리를 계산할 수 없다. 

• 방문할 수 있는 노드가 있다면 바로 방문하기에 최단 거리가 될 수 없다. 
• 예를들어 최단거리가 아닌 중간에 다른 노드를 거쳐 거쳐 탐색할 수 있기 때문이다. 

4. 노드 방문 표시에 대한 차이 

• DFS: Boolean visited[노드 번호] 를 이용해 이미 방문한 노드의 재방문을 막는다. 
• BFS: Boolean discovered[노드 번호] 를 이용해 방문 예정인 노드의 재방문을 막는다. 
  • BFS는 탐색중 발견한 노드를 큐에 넣고 discovered에 방문 예정으로 표시한다. 
  • 이후 FIFO에 따라 발견했던 순서대로 방문하게 된다. 
  • discovered는 큐에 노드가 두 번 들어가는 것을 방지해준다. 

 

노드 구성 자료구조에 따른 시간복잡도

참고 자료

인접행렬, 인접리스트 비교

 

1) 인접행렬, O(모든노드 x 간선)

• 모든 노드를 방문하며, 인접한 노드를 모두 검사해야 한다.

2) 인접 리스트, O(모든노드 + 간선)

• 노드에서 인접한 간선만 검사하면 되기 때문에 중복 간선 검사를 하지 않아도 된다.