DFS BFS 기본 구현

그래프를 나타내는 방법:

1.인접 행렬(adjacent matrix):메모리 소모가 큰 대신 탐색 속도가 빠르다
2.인접 리스트(adjacent list):메모리 소모가 작은 대신 탐색 속도가 느리다

1의 경우 그래프의 모든 노드에 맞는 (예 v개의 노드 이면 v**2) 행렬을
모두 구현해야 하므로 메모리가 소모가 큰 대신
탐색 속도가 m[vertex1][vertex2]으로 O(1)이다.

2의 경우 연결 상태 만큼의 사이즈가 필요하여 메모리 소모는 작지만
탐색할 경우 l[targetVertex]전체의 원소를 탐색 해야하므로
v개의 노드가 있을때 v1과 v2의 연결 상태를 탐색하는데 최악의 경우 O(v)를 소모한다.

DFS

스택을 이용하여 구현하는 그래프 탐색 알고리즘
일반적으로 구현할 때 스택을 직접 구현하지 않고 재귀 함수를 이용하여
함수 호출 스택을 이용하여 스택을 간접적으로 구현하여 사용한다.

BFS

큐를 이용하여 구현하는 그래프 탐색 알고리즘으로 일반적으로 dfs보다 성능이 좋다.

예제

import java.io.*;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;

class Main {
  static int[][] graph = {
	  {},
    {2,3,8},
    {1,7},
    {1,4,5},
    {3,5},
    {3,4},
    {7},
    {2,6,8},
    {1,7}
};
  static boolean[] vstDFS= new boolean[9], vstBFS = new boolean[9];
  public static void main(String[] args) throws IOException{
    dfs(1);
    System.out.println();
    bfs(1);
  }
  public static void dfs(int v){
    vstDFS[v] = true;
    System.out.print(v+" ");
    for (int v2:graph[v]){
      if(!vstDFS[v2]) dfs(v2); // 방문하지 않은 노드 재귀 함수 호출하여 스택에 적재
    }
  }
  public static void bfs(int v){
    Queue<Integer> q = new LinkedList<>();
    q.offer(v);
    vstBFS[v] = true;
    while(!q.isEmpty()){
      int curV = q.poll();
      System.out.print(curV+" ");
      for (int v2:graph[curV]){
        if(!vstBFS[v2]) {
          q.offer(v2);
          vstBFS[v2] = true;
        }// 방문하지 않았으면 큐에 삽입한다.
      }
    }
    System.out.println();
  }
}

출력:
1 2 7 6 8 3 4 5 (dfs)
1 2 3 8 7 4 5 6 (bfs)