[알고리즘] 그래프 탐색 알고리즘 DFS / BFS

DFS : 깊이 우선 탐색

개념

루트노드 (혹은 임의의 다른 노드)에서 시작하여 다음 분기(branch)로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법. 깊게 탐색함.

특징

• 자기 자신을 호출하는 순환알고리즘의 형태

알고리즘

• 출발 vertex인 V의 인접리스트부터 방문
• V에 인접함과 동시에 아직 방문하지 않은 vertex인 W를 선택
• W를 시작점으로하여 다시 깊이 우선 탐색 시작

code

void dfs(int v) {
	Node w;
    visited[v] = true;
    // v 출력
    for(w=graph[v];w;w=w.link) {
    	if(!visited[w.vertex]) dfs(w.vertex);
    }
    
}

BFS : 너비 우선 탐색

개념

루트노드 (혹은 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법. 넓게 탐색함.

특징

• 재귀적으로 동작하지 않음
• 자료구조 Queue를 사용
  - 선입선출 (FIFO) 원칙으로 탐색
  

알고리즘

• 출발 vertex인 v의 인접리스트부터 방문
• v에 인접한 모든 vertex를 먼저 방문
• 그 후, v에 인접한 첫번째 vertex에 인접한 vertex들 중에서 아직 방문하지 않은 vertex들을 다시 차례대로 방문 -> Queue 사용

code

void bfs(int v) {
	Node w;
    Queue<Integer> q = new LinkedList<>();
    visited[v] = true;
    q.add(v);
    while(q.isEmpty()) {
    	v = q.remove();
        // v 출력
        for(w=graph[v];w;w=w.link) {
        	if(!visited[w.vertex]) {
            	// w 출력
                g.add(w.vertex);
                visited[w.vertex]= true;
            }
        }
    }
    
}

DFS / BFS

구현

DFS: 스택이나 재귀함수로 구현
BFS: 큐로 구현

시간복잡도

• 그래프 탐색에서 두 방식의 시간복잡도는 동일함
• 노드 방문 여부 확인 시간 + 노드 방문하는 시간

문제 응용

• 경로의 특징 저장이 필요한 문제 : DFS 이용
  ex) 각 정점에 숫자가 적혀있고 a부터 b로 가는 경로를 구하는데, 경로에 같은 숫자가 있어서는 안 된다.

• 최단거리를 구하는 문제 : BFS 이용
  -> DFS로 경로를 탐색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 먼저 찾아지는 해답이 곧 최단거리이다.