[알고리즘]그래프 탐색하기: BFS & DFS

  그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 순회 문제(graph traversal problem)이라고 합니다. 

 

 그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제(graph search problem)이라고도 합니다. 

 

 그래프 탐색에서 아직 방문하지 않은 노드들 중 다음으로 살펴볼 노드들의 리스트를 open list, 방문한 노드들의 리스트를 closed list라고 말합니다. 

 

 그래프 탐색 알고리즘으로 너비 우선 탐색(BFS, Breadth-First Search)와 깊이 우선 탐색(DFS, Depth-First Search)가 있습니다. 

 

 

 

• 너비 우선 탐색(BFS, Breadth-First Search)

 BFS는 탐색 과정에서 방문할 노드의 순서를 기억할 자료구조로 Queue를 사용합니다. 즉 open list로 queue를 사용합니다. 

 

 closed list는 visit을 저장하는 배열을 사용하여 방문한 노드는 방문 표시를 해야합니다. 방문한 노드를 또 방문하는 것을 막기 위해서입니다. 

 

 시작 노드와 같은 거리, 즉 인접한 노드들의 방문 순서는 임의로 정해도 되지만, 반드시 시작 노드에서 가까운 노드부터 방문해야 합니다. 

 

 즉, 현재 노드에서 모든 자식 노드를 먼저 방문한 뒤, 손자 노드를 방문합니다. 

 

[탐색 과정]

  (1) 시작 노드를 Queue에 push

  (2) Queue에서 다음 살펴볼 노드 v를 pop

  (3) 노드 v를 이전에 방문했는지 확인(방문했다면 (2)번으로)

  (4) 노드 v 방문 표시

  (5) 노드 v에 인접한 노드들 중 아직 방문하지 않은 노드 w를 Queue에 push

  (6) Queue가 empty일 때까지 (2)~(5) 과정 반복

 

 

출처: https://developer-mac.tistory.com/64

• 장단점

장점	단점
1. 최단 경로 존재 시, 항상 최단 경로를 찾아줌  2. 검색 속도는 DFS보다 빠름  3. 그래프의 깊이가 얕고 노드의 수가 적을 때 적합	1. 그래프의 깊어질수록 상당한 메모리가 필요함  2. 유한 그래프에서 해가 없을 때, 그래프를 모두 탐색한 후에도 해를 찾을 수 없음  3. 무한 그래프에선 해를 찾을 수도 없고 탐색이 끝나지 않음

 

• 깊이 우선 탐색(DFS, Depth-First Search)

 DFS는 탐색 과정에서 방문할 노드의 순서를 기억할 자료구조로 Stack을 사용합니다. 즉 open list로 stack을 사용합니다. 또는 재귀함수를 사용합니다. 

 

 역시 closed list는 visit을 저장하는 배열을 사용하여 방문한 노드는 방문 표시를 합니다. 방문한 노드를 또 방문하는 것을 막기 위해서입니다. 

 

 BFS가 시작 노드에서 점차 탐색 범위를 넓혀 나가는 방식이라면, DFS는 시작 노드에서 시작하여 특정 경로를 따라 가능한 깊이 있는 노드을 재귀적으로 먼저 방문하는 방식입니다. 

 

[탐색 과정]

  (1) 시작 노드를 Stack에 push

  (2) Stack에서 다음 살펴볼 노드 v를 pop

  (3) 노드 v를 이전에 방문했는지 확인(방문했다면 (2)번으로)

  (4) 노드 v 방문 표시

  (5) 노드 v에 인접한 노드들 중 아직 방문하지 않은 노드 w를 Stack에 push

  (6) Stack이 empty일 때까지 (2)~(5) 과정 반복

 

 

출처: https://developer-mac.tistory.com/64

 

• 장단점

장점	단점
1. BFS보다 간단  2. 저장 공간이 많이 요구되지 않음  3. 목표 노드가 깊이 있을 때 빠르게 찾을 수 있음	1. 검색 속도 자체는 BFS보다 느림  2. 찾은 해가 최적의 해라는 보장이 없음

 

 

 

 

• BFS vs DFS 비교

BFS	DFS
Queue로 구현	Stack 또는 재귀함수로 구현
항상 최적 해	최적의 해라는 보장은 없음
그래프 규모가 작을 때	그래프 규모가 클 때
최단 경로를 찾을 때 사용	특정 목표 노드를 찾을 때 사용