그래프 탐색 - DFS & BFS

*️⃣ 그래프는 여러 개의 노드(node)와 이들을 연결하는 간선(Edge)으로 이루어진 자료구조이다.

	그래프	트리
방향성	방향/무방향 그래프	방향 그래프
순환성	순환/비순환	비순환
루트 노드	존재하지 않음	존재
노드간 관계성	부모, 자식 관계 없음	부모, 자식 관계

 

 

*️⃣ 그래프 탐색

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
• 시작점에서 간선(Edge, E)을 타고 이동할 수 있는 정점(Vertex, V)들을 모두 찾는 것
• 그래프 탐색 알고리즘에는 흔히 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있디.

 

*️⃣  깊이 우선 탐색(Depth-First Search, DFS)

: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색

#️⃣ 깊이 우선 탐색 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. -> 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
  
  

#️⃣ 깊이 우선 탐색 과정

 

 

 

*️⃣  너비 우선 탐색(Breadth-First Search, BFS)

: 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색

#️⃣ 너비 우선 탐색 특징

• 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다.
• 재귀적으로 동작하지 않는다.
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. -> 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
• 즉, 선입선출(FIFO) 원칙으로 탐색
  
  

#️⃣ 너비 우선 탐색 과정

 

 

*️⃣  DFS와 BFS 비교

• DFS는 특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다. DFS는 가능한 한 깊이 내려가면서 탐색을 진행하기 때문.

➔ 검색 대상 그래프가 큰 경우 (정점과 간선의 개수가 많음)
➔ 경로의 특징을 저장해둬야 하는 문제
ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제 (BFS는 경로의 특징을 가지지 못함)

• BFS는 최단 경로를 찾는 데 유용하다. BFS는 인접한 노드를 먼저 탐색하기 때문.

➔ 미로찾기 등 최단거리를 구해야 할 경우 (DFS는 처음으로 발견되는 해답이 최단거리 라는 것이 보장이 안된다. 반면 BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 곧 최단거리이다.)