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

DFS와 BFS 알고리즘

오늘은 그래프를 탐색하는 방법에 대해 포스팅하고자 한다.

그래프는 정점(Vertex)과 간선(Edge)으로 이루어져 있다.

간선을 통해 모든 정점을 방문하는 것을 그래프의 탐색이라 한다.

그래프를 탐색하는 방법에는 DFS와 BFS 방식이 있다.

먼저 그래프는 표현하는 방법으로 인접행렬, 인접리스트에 대해 알아보도록 하자.

1. 인접 행렬과 인접 리스트

---

1.1 인접행렬

그래프의 상태를 나타내는 정사각행렬이다.

그래프의 정점(Vertex)이 n 개일때, 그래프의 표현을 n*n의 이차원 배열로 나타낼 수 있다.

정점간의 간선이 존재하면 값을 1로 하고, 간선이 없으면 0으로 나타낸다.

인접행렬을 JAVA 언어로 나타내면 다음과 같다.

int[][] matrix = new int[n+1][n+1];
 
for(int i = 0 ; i < n ; i++){
    int v1 = s.nextInt();
    int v2 = s.nextInt();
 
    a[v1][v2] = 1;
    a[v2][v1] = 1;
}

1.2 인접리스트

한 정점과 연결되어 있는 모든 정점들을 하나의 연결리스트로 표현하는 방식이다.

그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장하여 표현한다.

인접행렬에 비해 변이 적은 그래프에 유용하다.

인접리스트를 JAVA 언어로 나타내면 다음과 같다.

ArrayList<Integer>[] a = (ArrayList<Integer[]) new ArrayList[n+1];
 
for(int i = 0 ; i <= n ; i++){
    a[i] = new ArrayList<>();
}
 
for(int i = 0 ; i < m ; i++){
    int v1 = s.nextInt();
    int v2 = s.nextInt();
 
    a[v1].add(v2);
    a[v2].add(v1);
}

자 그러면 이제 그래프의 탐색에 대해 본격적으로 알아보도록 해보자

DFS, BFS의 탐색 순서는 다음과 같다.

2. 깊이 우선 탐색

---

깊이우선탐색 (DFS;Depth First Search)은 트리나 그래프에서 한 루트로 탐색하다가 최대한 깊숙히 들어가 확인 후 다시 돌아가 다른 루트를 탐색하는 방식이다.

여기에서 부모노드로 되돌아오는 과정을 백트래킹(Backtracking)이라 한다.

일반적으로 인접행렬을 이용한  재귀호출을 사용하여 구현하지만, 단순한 스택배열로 구현하기도 한다.

장점

- 현 경로상의 노드만 기억하면 되므로 저장공간의 수요가 적다.

- 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

- 해가 없는 경로에 깊이 빠질 위험이 있다. 따라서 깊이제한(Depth bound)를 지정하여 해당 깊이 까지만 탐색하고, 목표 노드를 발견하지 못하면 다음의 경로를 따라 탐색하도록 하는 것이 좋다.

- 얻어진 해가 최단 경로가 된다는 보장이 없다. 목표까지의 경로가 다수인 경우 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리기 때문이다.

소스 코드로의 구현

DFS는 인접 행렬로 구현한다.

public static void dfs(int v) {
    System.out.print(v);
    check[v] = true;
    for(int i = 1 ; i < 1001; i++) {
        if(node[v][i] == 1 && !check[i]) {
            System.out.print(" ");
            dfs(i);
        }
    }
}

3. 너비 우선 탐색

---

너비 우선 탐색 (BFS;Breadth First Search)은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더이상 방문하지 않은 정점이 없을때까지 방문하지 않은 모든 정점들에 대해서 너비우선탐색을 적용한다.

장점

- 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

단점

- 경로가 매우 길 경우 탐색 가지가 급격히 증가하여, 많은 기억 공간을 필요로 한다.

- 해가 존재하지 않는 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝난다.

- 무한 그래프의 경우 끝낼 수 없다.

소스 코드로의 구현

BFS는 자료구조 Queue를 사용하여 구현하는 경우가 일반적이다.

public static void bfs(int v) {
    Queue<Integer> q = new LinkedList();
    q.add(v);
    check[v] = true;
        
    while(!q.isEmpty()) {
        int tmp = q.poll();
        System.out.print(tmp + " ");
        for(int i = 1 ; i < 1001; i++) {
            if(node[tmp][i] == 1 && !check[i]) {
                check[i] = true;
                q.add(i);
            }
        }
    }
}

정점의 개수가 1000개인 경우, BFS 탐색 수행 JAVA 소스코드