[JAVA] DFS, BFS 개념 설명

DFS, BFS를 공부하기 전에 그래프가 무엇인지 잘 모르겠다면 아래 링크에서 개념 보고 오기를 추천합니다!
👉 그래프 개념 보러 가기

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

<특징>
1. 인접한 숫자 중 가장 작은 노드부터 돌아간다
2. 현 경로상의 노드만 기억, 저장공간 수요 적다
3. 목표노드 깊은단계 있을 시 해를 빨리 구할 수 있다

but, 해가 없고 경로가 깊으면 탐색 시간 오래 걸린다 / 얻어진 해가 최단 경로라는 보장이 없다

구현 방법

구현방법은 2가지로 인접행렬과 인접리스트를 이용하는 방식이 있다.
인접행렬은 2차원 배열을 이용하기 때문에 메모리를 많이 차지하고 유연하지 않아 어려운편이다.
이에 비해 인접리스트는 리스트를 사용하기 때문에 쉽고 편리하다. 그러므로 나는 인접리스트를 사용하며 가장 기초적인 탐색인 모든 정점을 탐색하는 방법을 아래에서 설명하겠다.

<인접리스트 사용 - 재귀 호출로 종단 지점까지 방문하는 방식>

• 구현에 필요한 객체들
  1. arrayList: 정점간의 관계를 담은 객체(ArrayList안에 새로운 arrayList2를 붙인게 포인트)
  2. visited: 정점을 방문했는지 체크하기위한 boolean 객체(배열)
     
     
• 구현방법
  1. 주어진 그래프가 가진 정점개수 만큼 arrayList2를 만들어 arrayList 인덱스 1부터 넣는다.
  2. 해당 정점에서 인접한 정점을 arrayList에서 인덱스로 찾아서 arrayList2에 모두 넣는다. (문제에 따라 정렬이 필요하면 추후 Collections.sort 이용해 정렬)
  3. 이후 DFS함수를 호출한다.
  4. DFS 함수 : 해당 정점에 방문했는지 visited에 입력한 후 해당 정점(인덱스) arrayList를 찾아 arrayList2를 반복한다.
         -> 방문하지 않은 정점이라면 다시 DFS함수를 호출한다.(재귀)

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

<특징>
1. 루트 노드나 임의의 노드에서 시작하여 인접한 노드를 모두 확인한 후 다음 depth를 탐색한다.
2. 간선의 길이가 모두 동일할 경우 최단거리를 구하는 알고리즘으로 사용된다.(구하는 데 걸리는 시간이 짧다)
   ∵ DFS는 모든 경로를 간 후 최단거리를 구하지만 BFS는 가장 처음 도착한 경로가 최단거리

구현 방법

구현방법은 2가지로 인접행렬과 인접리스트를 이용하는 방식이 있다.
특징은 DFS와 동일하다. 인접리스트를 사용하며 가장 기초적인 탐색인 모든 정점을 탐색하는 방법을 아래에서 설명하겠다.

<인접리스트 사용 - 큐로 종단 지점까지 방문하는 방식>

• 구현에 필요한 객체들 - DFS와 동일
  1. arrayList: 정점간의 관계를 담은 객체(ArrayList안에 새로운 arrayList2를 붙인게 포인트)
  2. visited: 정점을 방문했는지 체크하기위한 boolean 객체(배열)
     
     
• 구현방법 - 3번(함수호출)까지 DFS와 동일
  1. 주어진 그래프가 가진 정점개수 만큼 arrayList2를 만들어 arrayList 인덱스 1부터 넣는다.
  2. 해당 정점에서 인접한 정점을 arrayList에서 인덱스로 찾아서 arrayList2에 모두 넣는다. (문제에 따라 정렬이 필요하면 추후 Collections.sort 이용해 정렬)
  3. 이후 BFS함수를 호출한다.
  4. BFS 함수 :
     • 큐를 생성해 시작 정점을 삽입하고 방문했다고 표시
     • 이후 큐에서 연결된 정점을 찾아 반복한다. (큐가 비어있을 때까지)

참고자료(youtube): 어라운드 허브 스튜디오-[자바로 배우는 자료구조] DFS, BFS