그래프 탐색 알고리즘 : DFS/BFS

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색알고리즘 DFS, BFS 자주 등장

DFS(Depth-First Search)

• DFS는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.
• DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같습니다.
  • 탐색 시작노드를 스택에 삽입하고 방문 처리합니다.
  • 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다,
  • 더이상 위에 과정을 수행 할수 없을때까지 반복합니다.

import java.util.*; // 스택

public class Main {

    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();

        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        s.push(5);
        s.push(2);
        s.push(3);
        s.push(7);
        s.pop();
        s.push(1);
        s.push(4);
        s.pop();
        // 스택의 최상단 원소부터 출력
        while (!s.empty()) {
            System.out.println(s.peek());
            s.pop();
        }
    }

}

import java.util.*;

public class Main { //재귀함수 조건

    public static void recursiveFunction(int i) {
        // 100번째 호출을 했을 때 종료되도록 종료 조건 명시
        if (i == 100) return;
        System.out.println(i + "번째 재귀 함수에서 " + (i + 1) + "번째 재귀함수를 호출합니다.");
        recursiveFunction(i + 1);
        System.out.println(i + "번째 재귀 함수를 종료합니다.");
    }

    public static void main(String[] args) {
        recursiveFunction(1);
    }

}

 

BFS(Breadth-First Search)

• BFS는 너비 우선 탐색이라고 부르며 그래프에서 가까운 노드부터 우선 탐색하는 알고리즘입니다.
• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다.
  • 탐색 시작노드를 큐에 삽입하고 방문 처리합니다.
  • 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입히고 방문 처리합니다.
  • 더이상 위에 과정을 수행 할수 없을때까지 반복합니다.

import java.util.*;

public class Main { // 큐

    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        q.offer(5);
        q.offer(2);
        q.offer(3);
        q.offer(7);
        q.poll();
        q.offer(1);
        q.offer(4);
        q.poll();
        // 먼저 들어온 원소부터 추출
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }

}