[그래프] DFS와 BFS 구현하기

알고리즘

[그래프] DFS와 BFS 구현하기 :: 마이구미

mygumi 2017. 1. 19. 22:15

이번 글은 자료구조 중 그래프를 다뤄본다.
백준 알고리즘 1260번을 통해 진행하니 참고하길바란다.

그래프는 정점과 간선으로 이루어진 자료구조의 일종이다. G = (V, E)

그림을 보다시피, 정점과 간선이 무엇을 나타내는 지 알 수 있다.

정점은 각 출발점 도착점과 같은 점이라고 보면 되고, 간선은 그 정점간 연결된 관계를 뜻한다.

무방향 그래프와 방향 그래프가 있다.

말그대로 방향이 있는 그래프는 2->1로만 갈 수 있고, 무방향이라면 2->1, 1->2 가능하다는 것이다.

여기서는 무방향 그래프를 기준으로 다뤄볼 것이다.

그래프의 탐색에 있어 DFS, BFS 방식이 있다.

깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 2가지 방식을 알아보자.

두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 있지만, 그 과정에서 탐색하는 방식의 차이가 있다.

아래 그림을 보는 게 가장 이해가 빠를 것이다.

일단 두 탐색의 차이는 눈으로 확인할 수 있다.

탐색 이름 그대로, 깊이, 너비를 기준으로 탐색하고 있다.

그림을 통해 어떻게 탐색하는지만 알아도 두 방식에서 나오는 장단점을 이해할 수 있다.

DFS는 스택을 사용하고, BFS는 큐를 사용한다.

구현에 있어서, 인접행렬 또는 인접리스트를 통해 구현할 수 있다.

DFS와 BFS에 앞서, 먼저 인접행렬과 인접리스트를 알아보자.

인접행렬과 인접리스트는 정점과 간선이라고 생각하면 된다.

인접행렬은 정점(V)이 n개일 때 N*N 이차원 배열로 나타낼 수 있다.

인접행렬을 일반적으로 a라고 이름을 짓는다. (성의없게 보이지만 일반적으로 그렇다고 한다)

a[1][5] = 1 의 의미는 정점 1과 정점 5의 간선이 연결되어 있다는 뜻이다.

무방향이기에 a[5][1] 또한 1이다. 빨간색을 통해 확인하자.

인접행렬의 값이 1이라면, 정점간의 간선이 존재한다는 것이고, 0이라면 존재하지 않는다는 것이다.

(현재는 가중치가 없지만, 가중치를 넣을 때는 1 대신 가중치를 넣으면 된다)

소스를 통해 나타내면 아래와 같다.

int[][] a = new int[n + 1][n + 1];

for (int i = 0; i < m; i++) {
    int v1 = sc.nextInt();
    int v2 = sc.nextInt();

    a[v1][v2] = 1;
    a[v2][v1] = 1;
}

이번엔 인접리스트를 보자.

인접행렬은 이차원 배열의 행과 열을 통해 정점간의 간선을 표현한거와는 다르다.

1에 연결되어있는 간선들을 A[1] 에 저장하고, A[2]에는 2에 연결되어있는 간선을 저장했다.

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 = sc.nextInt();
    int v2 = sc.nextInt();

    a[v1].add(v2);
    a[v2].add(v1);

}

같은 목적이지만 배열과 리스트를 통해 다르게 저장함으로써 큰 차이를 볼 수 있다.

인접행렬은 크기가 정점과 간선의 갯수와 사관없이 정점갯수 * 정점갯수 이기 때문에 공간복잡도가 O(v^2) 이다.

하지만 인접리스트는 필요한 공간만 쓰기 때문에 O(V+E) 가 된다.

인접행렬이 익숙하고, 조금 더 쉽게 이해할 수 있어 많이 사용한다.

하지만 보다시피 인접행렬을 쓰는 것보다는 인접리스트가 효율적이다.

이젠 DFS와 BFS를 구현해보자.

DFS와 BFS의 또하나의 차이점은 DFS는 스택을 사용하고, BFS는 큐를 사용하는 것이다.

위에서 말했듯 두 방식의 목표는 모든 정점을 한번만 탐색하는 것이므로, 탐색여부를 확인하기 위한 check 배열이 필요하다.

먼저 DFS를 보자. (인접 행렬로 진행하겠다.)

스택을 사용한다고 하지만 많은 글들에서 재귀를 통해 구현하는 것을 많이 봤을거라 생각한다.

public static void dfs(int[][] a, boolean[] c, int v) {
    int n = a.length - 1;

    c[v] = true;
    System.out.print(v + " ");

    for (int i = 1; i <= n; i++) {

        if (a[v][i] == 1 && !c[i]) {
            dfs(a, c, i);
        }

    }

}

이해를 돕기 위해 재귀를 스택으로 바꿔서 보자.

a는 인접행렬이고, c는 방문여부, v는 정점이 된다.

public static void dfs(int[][] a, boolean[] c, int v, boolean flag) {
		Stack<Integer> stack = new Stack<>();
		int n = a.length - 1;

		stack.push(v);
		c[v] = true;
		System.out.print(v + " ");

		while (!stack.isEmpty()) {
			int vv = stack.peek();

			flag = false;

			for (int i = 1; i <= n; i++) {

				if (a[vv][i] == 1 && !c[i]) {
					stack.push(i);
					System.out.print(i + " ");

					c[i] = true;
					flag = true;
					break;
				}

			}

			if (!flag) {
				stack.pop();
			}

		}

	}

1. 스택의 top에 있는 정점을 기준으로 간선이 연결되어있고 아직 방문하지 않은 정점을 찾는다.

2. 조건에 맞는 정점을 찾는다면 해당 정점을 스택에 넣은 후 break를 건다.

3. 연결된 간선이 없고, 방문하지 않은 정점을 찾지 못한다면 pop.

2번에서 break를 걸어줌으로써, 바로 DFS 탐색이 진행된다.

현재 정점을 기준으로 탐색 중 조건에 맞는 정점을 찾는다면 그 정점을 기준으로 다시 탐색을 한다.

이를 반복함으로써 위 DFS의 그림처럼 깊이 탐색을 할 수 있게 되는 것이다.

3번에서 경우는 DFS와 BFS를 비교하는 그림에서 보듯 1, 2, 3을 탐색한 후 더이상 탐색할 수 없다.

이런 경우를 다시 돌아가기 위해 pop을 하는 것이다.

위와 같이 스택을 통해 구현한 것이 재귀로 바꾼 것 뿐이다.

다른 점은 없다. 단순히 재귀로 바꾼 것 뿐이다.

이번엔 BFS를 보자.

위에서 말했듯이 BFS는 큐를 사용한다.

public static void bfs(int[][] a, boolean[] c, int v) {
    Queue<Integer> q = new LinkedList<>();
    int n = a.length - 1;

    q.add(v);
    c[v] = true;

    while (!q.isEmpty()) {

        v = q.poll();
        System.out.print(v + " ");

        for (int i = 1; i <= n; i++) {

            if (a[v][i] == 1 && !c[i]) {
                q.add(i);
                c[i] = true;
            }

        }
    }

}

BFS의 경우는 아래와 같다.

1. 큐의 front인 정점을 기준으로 연결된 간선이 있고, 방문하지 않은 정점을 찾는다.

2. 조건에 맞는 정점은 모두 큐에 넣는다.

위 과정을 반복한다.

DFS의 경우에는 break문을 걸어줬다.

하지만 BFS는 모두 큐에 넣음으로써 이름처럼 너비를 기준으로 탐색한다.

그렇기에 모든 경우를 탐색할 수 있게 됨으로써, 최단 경로에 이용한다고도 말을 할 수 있는 것이다.

마지막으로 인접 리스트를 조금 더 보겠다.

위에서 공간복잡도를 통해 인접행렬과 비교를 해보았다.

시간복잡도 측면에서도 효율적이다. 이유를 보자.

while(!q.isEmpty()) {
    v = q.poll();
    System.out.print(v + " ");

    for (int vv : a[v]) {

        if (!c[vv]) {
            q.add(vv);
            c[vv] = true;
        }

    }

}

인접 행렬의 경우 정점을 탐색하는 과정에서 무조건 1에서 n까지 루프를 돌았다.

인접 리스트의 경우에는 리스트 특성상 각 리스트마다 존재하는 정점만큼 존재한다.

그렇기에 i에서 n까지 돌지 않아도 되고, 위와 같이 존재하는 만큼만 탐색하면 된다.

인접 리스트의 경우는 Github을 통해 확인하길 바란다.

단순히 인접행렬과 인접리스트의 차이다.

깊게 생각해서 헷갈리지 말길 바란다.

DFS 와 관련 있는 백트래킹은 다음 링크를 참고하면 된다.

http://mygumi.tistory.com/191

아래 링크의 백준 알고리즘 1260번 문제는 BFS와 DFS의 가장 기본이 되는 문제이다.

꼭 풀어보길 바란다.

전체 소스는 GitHub을 통해 확인하길 바란다.

방향 그래프는 아래 11403번 문제 관련 글을 보면 된다.