DFS/BFS 알고리즘

* DFS, BFS는 그래프를 탐색하는 방법

그래프란?

• 노드(N, node)와 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료구조
• 정점,Vertex(=노드)과 간선으로 이루어진 자료구조의 일종이다. G=(V,E))
• 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.
  ex) 지도, 지하철노선도, 전기회로, 도로, 선수과목 등
• 트리도 그래프의 한 종류이다! 단, 방향성이 있는 비순환 그래프이다.
• 순회는 DFS나 BFS로 이루어진다!

DFS란?

• Depth First Search의 약자로 깊이 우선 탐색을 뜻한다.
• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 법
• 즉, 넓게(Wide)하게 탐색하기 전에 깊게(Deep) 탐색하는 것이다!!
• 스택을 사용한다.
• DFS를 사용하는 경우 : 모든 노드를 방문하고자 할 때

BFS란?

• Breadth First Search의 약자로 넓이 우선 탐색을 뜻한다.
• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 즉, 깊게(Deep) 탐색하기 전에 넓게(Wide) 탐색하는 것이다.
• 큐를 사용한다.
• BFS를 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때

• 지구상에 존재하는 모든 친구 관계를 그래프로 표현 후 Ash와 Vanessa 사이의 경로를 찾는 경우
  • 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
  • 넓이 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색한다.