DFS

깊이 우선 탐색 , Depth-First Search

• 가능한 깊게 그래프를 탐색하는 방법
• 더 이상 진행할 수 없을 때까지 한 방향으로 깊이 탐색한 후 되돌아와 다른 방향의 노드를 탐색
• 이 방법은 스택(Stack) 또는 재귀 함수(Recursive Function)를 이용하여 구현

특징

1. 메모리 소비가 BFS에 비해 적을 수 있음
2. 경로의 해답이 깊은 단계에 있을 경우 효과적
3. 모든 가능한 경우의 수 중에서 최적의 해를 찾아야 할 때 사용됨

/* 인접 리스트 이용 */
class Graph {
  private int V;
  private LinkedList<Integer> adj[];
 
  Graph(int v) {
      V = v;
      adj = new LinkedList[v];
      // 인접 리스트 초기화
      for (int i=0; i<v; ++i)
          adj[i] = new LinkedList();
  }
  void addEdge(int v, int w) { adj[v].add(w); }
   
  /* DFS */
  void DFS(int v) {
      boolean visited[] = new boolean[V];
 
      // v를 시작 노드로 DFSUtil 재귀 호출
      DFSUtil(v, visited);
  }
  
  /* DFS에 의해 사용되는 함수 */
  void DFSUtil(int v, boolean visited[]) {
      // 현재 노드를 방문한 것으로 표시하고 값을 출력
      visited[v] = true;
      System.out.print(v + " ");
 
      // 방문한 노드와 인접한 모든 노드를 가져온다.
      Iterator<Integer> it = adj[v].listIterator();
      while (it.hasNext()) {
          int n = it.next();
          // 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
          if (!visited[n])
              DFSUtil(n, visited);
      }
  }

}

BFS

넒이 우선 탐색, Breadth-First Search

• BFS는 가장 가까운 노드부터 방문하고 그 다음으로 가까운 노드를 방문하는 방식
• 큐(Queue)를 사용하여 구현

특징

1. 모든 노드를 최소 비용으로 탐색하는 데 유리
2. 최단 경로를 찾거나 장애물이 적은 경로를 찾는 데 사용됨
3. 메모리 소비가 DFS보다 클 수 있음

class Graph {
  private int V;
  private LinkedList<Integer> adj[];
 
  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i)
      adj[i] = new LinkedList();
  }
 
  void addEdge(int v, int w) { adj[v].add(w); }
 
  /* BFS */
  void BFS(int s) {
    boolean visited[] = new boolean[V]; //방문여부 확인용 변수
    LinkedList<Integer> queue = new LinkedList<Integer>(); //연결리스트 생성
 
    visited[s] = true;
    queue.add(s);
 
    while (queue.size() != 0) {
      // 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
      s = queue.poll();
      System.out.print(s + " ");
 
      // 방문한 노드와 인접한 모든 노드를 가져온다.
      Iterator<Integer> i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        
        // 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }
}

참조
https://devuna.tistory.com/32