[java] DFS, BFS 알고리즘

DFS (깊이 우선 탐색)

시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법

• 재귀함수 또는 스택으로 구현
• 노드 방문 시 반드시 방문 여부 검사
  isVisit[idx] = true;
• 구현은 BFS에 비해 간단하나 검색 속도는 BFS에 비해 느림

void main() {
  int[] numbers = {1, 2, 3, 4, 5};
  boolean[] visit = {false, false, false, false, false};
  
  dfs(numbers, 0, visit);
}

void DFS(int[] numbers, int idx, boolean[] visit) {
  visit[idx] = true;

  for(int i : numbers) {
     if(!visit[i])
       	  DFS(numbers, i, visit);
  }
}

BFS (너비 우선 탐색)

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 큐에 이웃하는 정점을 담아놓고 차례대로 pop() 하여 구현
• 노드 방문 시 반드시 방문 여부 검사
  isVisit[idx] = true;
• 재귀 방식인 DFS에 비해 정점을 저장할 저장공간이 많이 필요함
• 탐색해야 할 노드의 수가 많다면 좋지 않음

void main() {
  int[] numbers = {1, 2, 3, 4, 5};
  boolean[] visit = {false, false, false, false, false};
  
  BFS(numbers, 0, visit);
}

void BFS(int[] numbers, int start, boolean[] visit) {
  Queue<Integer> queue = new LinkedList();
  queue.add(start);
  visit[start] = true;
  
  while(!queue.isEmpty()) {
     int next = queue.poll();
    
     for(int i : numbers) {
       if(!visit[i]) {
         queue.add(i);
         visit[i] = true;
       }
   }
}