[Java]BFS / DFS

그래프의 탐색은 모든 정점을 한 번씩 방문하는데 그 목적이 있다.

 

지도 애플리케이션에서 두 지점 사이의 경로를 검색할 경우를 생각 해보면,

 

최소 시간이나 최소 환승 등 여러 가지 검색 기준이 있다.

 

이와 비슷하게 그래프의 모든 정점을 방문하는 방법에도 크게 두 종류가 있는데,

 

BFS(Breadth-First Search) - 너비 우선 탐색과 DFS(Depth-First Search) - 깊이 우선 탐색이 그것이다.

 

---

BFS(Breadth First Search)

너비 우선 탐색(BFS)은 시작 정점부터 가장 가까운 순서대로 정점을 방문하는 방법이다.

 

최초 시작 정점과 인접한 정점을 모두 방문한 뒤, 각 순회된 정점부터 시작하여 인접한 정점을 방문하는 방식을 반복한다.

 

출처: https://minhamina.tistory.com/36?category=837168

[Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현

그래프의 일종인 트리구조에서 레벨 순회(Level Order Traversal)가 이 BFS에 속한다.

 

두 노드 사이의 최단경로를 찾고 싶을 때 사용하는 것이 바로 이 BFS이며,

 

재귀적으로 동작하지 않기 때문에 선입선출이 중요한 큐를 사용해서 구현한다.

 

1. 시작 노드를 방문한다.
    
   • 큐에 시작 노드를 삽입(enqueue)한다.
   • 초기 상태의 큐에는 시작 노드만 저장
2. 큐에서 꺼낸 노드와 인접한 노드들을 큐에 추가한다.
   
   
   • 큐에서 꺼낸 노드를 방문한다.
   • 큐에서 꺼낸 노드와 인접한 노드를 순서대로 순회한다.
   • 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
   • 큐에 순회된 노드를 삽입(enqueue)한다.
3. 큐가 공백 상태가 될 때까지 계속한다.

 

---

DFS(Depth-First Search)

 

깊이 우선 탐색(DFS)은 하나의 경로를 끝까지 탐색한 후 뒤로 돌아와 다른 경로를 방문하는 방식이다.

 

출처: https://minhamina.tistory.com/22?category=837168

[Java] DFS 깊이 우선 탐색 - 인접리스트 / 인접행렬로 구현

모든 노드를 방문하고 싶을 때 주로 사용되는 것이 바로 이 DFS이다.

 

BFS와 비교했을 때 가장 큰 특징은 백트래킹(Backtracking)인데, 탐색을 마친 후 이전의 정점으로 돌아오는 것을 뜻한다.

 

DFS의 구현방법은 재귀 함수를 이용하는 방법과 스택을 이용하는 방법이 있으며,

 

검색 속도 자체는 BFS에 비해 느리지만 알고리즘이 더 간단하다.