그래프 탐색 - 깊이 우선 탐색 & 너비 우선 탐색

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

깊이 우선 탐색은 직관적인 그래프 순회 방식이다.
임의의 시작 노드를 설정하고 간선을 따라 이동해 가며 도달 가능한 모든 노드를 처리한다. 
더 이상 갈 수 없는 노드까지 탐색한 후, 이전노드로 돌아가 그래프의 다른 부분을 탐색하기 시작한다.
방문했던 노드를 기록하므로 각 노드는 한 번씩만 처리된다.

1번 노드를 시작으로 정하고, 더 이상 갈 수 없을 때까지 순회한다. 즉 1 -> 2 -> 3 -> 5 순으로 방문한 뒤, 다시 1번 노드로 돌아간다. ( 2번 노드는 이미 방문한 노드이기 때문에 다시 방문하지 않는다. )
그런 다음 방문하지 않는 노드인 4번 노드를 방문한다.

DFS 구현

import java.util.ArrayList;
import java.util.Vector;

public class DFS {
	//인접 리스트
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(5);

	//방문한 노드
	static Vector<Boolean> visited = new Vector<Boolean>(5);

	public static void main(String[] args) {
		//그래프 생성
		for(int i = 0 ; i < 5 ; i++) {
			adj.add(new ArrayList<Integer>());
		}
		adj.get(0).add(1);
		adj.get(0).add(3);
		adj.get(1).add(2);
		adj.get(1).add(4);
		adj.get(2).add(3);
		
		//방문 노드 false로 초기화
		for(int i = 0 ; i < 5 ; i++ ) {
			visited.add(i, false);
		}
		
		dfs(0);
	}

	public static void dfs(int s) {
		//이미 방문한 노드는 생략
		if(visited.get(s)) {
			return;
		}

		//방문 노드 출력
		System.out.println(s+"노드 방문");

		//방문 표시
		visited.set(s, true);

		//인접 리스트에 있는 노드들 방문
		for( int u : adj.get(s)) {
			dfs(u);
		}
	}

}

깊이 우선 탐색의 시간 복잡도는 O(n+m)으로, n은 노드의 개수이고, m은 간선의 개수이다. 
이러한 시간 복잡도를 갖는 이유는 각 노드와 간선을 한번씩 처리하기 때문이다.

 

 

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

너비 우선 탐색은 시작 노드에서 각 노드까지의 거리가 증가하는 순서대로 노드를 방문하는 방식이다.
특정한 시작 노드에서 다른 모든 노드까지의 거리를 너비 우선 탐색을 이용하여 계산할 수 있다.
하지만 깊이 우선 탐색보다 구현하기 어렵다는 단점이 있다.

우선, 시작 노드에서 거리가 1인 노드를 모두 방문한 뒤, 그 다음으로는 거리가 2인 노드를 방문하고 이러한 방식을 모든 노드를 방문 할 때까지 반복한다.

시작 노드를 1로 지정한 뒤, 거리가 1인 2번 노드, 4번 노드를 방문한다. 그리고, 거리가 2인 3번 노드와 5번 노드를 방문한다. 마지막으로 거리가 3인 6번 노드를 방문한 뒤 종료한다.

BFS 구현

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

public class BFS {
	//인접 리스트
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(5);

	//방문한 노드
	static Vector<Boolean> visited = new Vector<Boolean>(5);
	
	//해당 노드까지의 거리
	static Vector<Integer> distance = new Vector<Integer>(5);
	
	//처리 큐
	static Queue<Integer> q = new LinkedList<Integer>();

	public static void main(String[] args) {
		//그래프 생성
		for(int i = 0 ; i < 6 ; i++) {
			adj.add(new ArrayList<Integer>());
		}
		adj.get(0).add(1);
		adj.get(0).add(3);
		adj.get(1).add(2);
		adj.get(1).add(4);
		adj.get(2).add(5);
		adj.get(4).add(5);
		
		//방문 노드 false로 초기화
		for(int i = 0 ; i < 6 ; i++ ) {
			visited.add(i, false);
		}
		
		//노드까지의 거리 초기화
		for(int i = 0 ; i < 6 ; i++ ) {
			distance.add(i, (int) Double.POSITIVE_INFINITY);
		}
		
		bfs(0);
	}

	public static void bfs(int x) {
		//방문 표시
		visited.set(x, true);
		
		//거리 0으로
		distance.set(x, 0);
		
		//방문 노드 출력
		System.out.println(x+"노드 방문, 거리: "+ distance.get(x));
		
		//처리할 노드에 추가
		q.add(x);
		while(!q.isEmpty()) {
			int s = q.poll();
			
			//가능한 모든 노드를 방문
			for(int u : adj.get(s)) {
				//이미 방문한 노드는 생략
				if(visited.get(u)) {
					continue;
				}
				//방문, 거리 설정
				visited.set(u, true);
				distance.set(u, distance.get(s)+1 );
				
				//방문 노드 출력
				System.out.println(u+"노드 방문, 거리: "+ distance.get(u));
				
				q.add(u);
			}
		}
		
		


	}

}

 우선 탐색의 시간 복잡도는 O(n+m)이다. n은 노드의 개수, m은 간선의 개수이다.