그래프의 탐색, bfs 와 dfs

1. 개요

그래프의 모든 정점을 방문하기 위한 방법으로 깊이우선탐색(depth first search)과 너비우선탐색(breadth first search) 가 있습니다.

깊이우선탐색은 하나의 정점에서 인접한 다음 정점을 방문한 뒤, 다시 새로 방문한 정점과 인접한 정점을 방문하는 방식으로, 한 우물만 죽어라 파는 방법입니다.

반면 너비우선탐색은 시작정점과 인접한 정점 모두를 방문한 뒤, 방문한 정점들 중에서 한 놈을 골라 그와 관련된 정점들을 모두 터는 방식입니다. 마치 저 반역자의 삼족을 멸하라! 하는 것처럼..

2. 알고리즘

(1) dfs

a. 정점 하나를 방문합니다.

b. 방문한 정점과 인접한 정점 중 방문하지 않은 정점 하나를 방문합니다.

c. 해당 정점을 중심으로 다시 깊이 우선 탐색을 시작합니다.

d. 만약 인접한 정점 중에 방문하지 않은 정점이 없다면 (막다른 길에 도달) 이전 정점으로 다시 되돌아가 탐색을 시작합니다.

(2) bfs

a 정점 하나를 방문합니다.

b. 방문한 정점과 인접한 정점 중 방문하지 않은 정점 모두를 방문합니다.

c. 방문한 정점 중 하나를 골라 다시 너비우선탐색을 시작합니다.

d. 마찬가지로 인접한 미방문 정점이 하나도 없다면 최근 방문한 정점 중 다른 하나를 골라 다시 탐색합니다.

3. 그림으로 이해하기

 

dfs 는 시작정점 1과 인접한 미방문 정점 4, 5 중 하나를 방문합니다. (보통 작은 수를 먼저 방문)

그리고 4와 인접한 미방문 정점 0과 2 중 하나, 0을 방문합니다.

그리고 0과 인접한 미방문 정점 2와 5 중 2를 방문합니다.

그리고 2와 인접한 미방문 정점 3을 방문합니다.

 

3과 인접한 정점은 2뿐인데 이미 방문했기 때문에 더 갈곳이 없습니다. 2로 돌아갑니다.

2도 마찬가지 상황입니다. 0으로 돌아갑니다.

0은 갈 곳이 있습니다 마지막으로 5를 방문합니다.

<방문순서> 1 - 4 - 0 - 2 - 3 - 5

이제 같은 그래프에서 bfs는 어떨지 봅시다.

1과 인접한 4, 5를 모두 방문합니다.

다음으로 4와 인접한 0, 2를 방문합니다.

그리고 5와 인접한 미방문 정점이 있는 지 살펴봤지만 없습니다.

그럼 최근 방문한 0, 2 를 봐야합니다. 0은 꽝입니다. 2는 .. 3이 남아있네요. 3을 방문합니다.

<방문순서> 1 - 4 - 5 - 0 - 2 - 3

4. 구현

우선 그래프를 어떻게 표현할 지 결정해야 합니다.

인접행렬이나 인접리스트 등 몇 가지 방법 중에 가장 간편한 인접행렬을 이용했습니다.

dfs 는 재귀함수를 이용해 간단하게 구현이 가능하지만

bfs 는 최근 방문한 정점과 인접한 정점들을 보관하기 위한 자료구조로, 큐가 필요합니다.

import java.util.*;

class Main {
    public static void main(String[] args) {
    
    	Scanner sc = new Scanner(System.in);
    	
    	int N = sc.nextInt(), M = sc.nextInt(), V = sc.nextInt();
    	int[] visited = new int[N+1];
    	int[][] graph = new int[N+1][N+1];
    	
        /* 사용자로부터 간선 정보를 받아 N X N 행렬에 저장합니다.*/
    	while(sc.hasNext()) {
    		int i = sc.nextInt(), j = sc.nextInt();
    		graph[i][j] = 1;
    		graph[j][i] = 1;   		
    	}
    	
    	dfs(graph, visited, V);
    	System.out.println();
    	
    	Queue<Integer> q = new LinkedList<Integer>();
    	q.add(V);
    	Arrays.fill(visited, 0);
    	while(!q.isEmpty()) bfs(q, graph, visited);
    	System.out.println();
    }
    
    public static void dfs(int[][] g, int[] v, int e) {
    	if(v[e]!=1) { // 미방문이라면
    		v[e] = 1; // 방문
    		System.out.print((e)+" ");
    		for(int i = 1; i < g.length; i++) { // 인접 정점을 탐색
    			if(g[e][i] == 1 && v[i]==0) dfs(g, v, i);
    		}
    	}
    	else return;
    }
    
    public static void bfs(Queue<Integer> q, int[][]g, int[]v) {
    	
    	if(q.isEmpty()) return;
    	int e = q.poll(); // 큐에서 새로운 정점을 하나 가져옴
    	
    	if(v[e] != 1) {
    		v[e] = 1;
    		System.out.print((e)+" ");
    		for(int i = 1; i < g.length; i++) { // 인접한 정점을 큐에 저장
    			if(g[e][i] == 1) q.add(i);
    		}
    	}
    	
    	else return;
    	
    }
}

 

5. 관련문제

https://www.acmicpc.net/problem/1260