DFS와 BFS

먼저 둘 다 어느 때 사용하는 지 구분하자면

모든 정점을 방문해서 뭔가를 해야 될 때는 둘 중 어떤 알고리즘을 써도 괜찮다.

 

경로의 특징을 저장할 때 ( ex. 경로의 가중치를 저장하여 사용 ...) 는 당연히 경로를 연결할 수 있는 DFS를 사용한다.

BFS는 노드가 연결된 방향대로 진행하지 않기 때문에 경로가 없어 사용할 수 없다.

 

최단거리나 최단 경로에는 BFS를 사용한다.

DFS를 사용하기엔 DFS는 한 방향으로 나아가 트리의 끝까지 진행하기 때문에 시간이 더 오래 걸리는 듯 하다.

 

그리고 작은 그래프에는 BFS를 사용하고, 아주 큰 그래프에는 DFS를 사용한다.

 

 

공통적으로 두 함수에 필요한 부분은

1. 노드의 방문 여부를 나타내는 boolean 배열

2. 트리의 정점과 노드를 2차원 연결 리스트로 변환한 리스트

 

이 때 트리를 연결 리스트로 바꿀 때 두 가지 방법이 있다.

1. 연결 리스트 LinkedList<Integer>[] graph;      O( n + m )

2. 행렬 그래프 int[][] graph;    O( n^2 )

 

두 방법 중 보통 연결 리스트를 많이 사용하고, 연결 리스트가 시간복잡도도 O( n + m )으로 더 짧은 것을 알 수 있다.

 

 

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

한 방향으로 진행하여 마지막 리프 노드까지 간 후 자식 노드가 더 없을 때 돌아서 다른 방향으로 노드 탐색을 진행한다.

 

DFS 알고리즘은 스택 또는 재귀 함수를 이용하여 생성한다.

보통은 스택보다 재귀 함수를 많이 사용하여 만드는 것 같으므로 재귀 함수로 설명하겠다.

 

재귀 함수로 만들 때 가장 중요한 것은 함수에 중단점을 반드시 만들어야 된다는 것이다.

 

DFS 알고리즘 코드

public static int V; //정점 개수
public static boolean[] visited = new boolean[V + 1];
public static LinkedList<Integer>[] graph;

public static void dfs(int v) { //새로운 매개변수를 추가
    visited[v] = true;
    System.out.println(v); //이 부분을 수정

    for (int nextV : graph[v]) {
        if (!visited[nextV]) {
            dfs(nextV); //매개변수로 들어갈 수 지정
        }
    }
}

 

 

 

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

왼쪽에서 오른쪽 방향으로 레벨 순서대로 진행한다.

루트 노드가 있는 1레벨부터 리프 노드가 있는 레벨까지 진행한다.

 

BFS 알고리즘은 Queue를 이용해 만든다.

 

BFS 알고리즘 코드

public static int V; //정점 개수
public static boolean[] visited = new boolean[V + 1];
public static LinkedList<Integer>[] graph;

public static void bfs(int v) { //새로운 매개변수를 추가
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(v);
    visited[v] = true;
    System.out.println(v); //이 부분을 수정

    while (!queue.isEmpty()) {
        int num = queue.poll();
        for (int nextV : graph[num]) {
            queue.offer(nextV);
            visited[nextV] = true;
        }
    }
}