[알고리즘] 자바에서의 BFS 와 DFS

BFS(Breadth-First-Search) 와 DFS(Depth-First-Search) 

BFS 와 DFS 는 대표적인 그래프 노드 탐색 알고리즘이다.

- 너비 우선 탐색(BFS) : 정점들과 같은 레벨에 있는 노드들(형제 노드들) 을 먼저 탐색하는 방식

- 깊이 우선 탐색(DFS) : 정점의 자식들을 먼저 탐색하는 방식

- 둘 다 트리와 같은 그래프 구조(사이클이 없는 그래프) 에서 데이터를 탐색하는 방식이다.

 

 

위와 같은 트리의 경우 BFS 와 DFS 는 각각 어떻게 동작할까?

* BFS 방식 : A - B - C - D - G - H - I - E - F - J

- 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회한다.

* DFS 방식 : A - B - D - E - F - C - G - H - I - J

- 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다.

 

자바로 그래프를 표현하는 방법(BFS 와 DFS 의 경우)

자바에서 제공하는 HashMap 클래스와 List 클래스를 활용해서 그래프를 표현할 수 있다.

- 각 노드들을 해시맵의 키(key) 로 만든다.

- 키가 있으면 당연히 그에 해당하는 값(value) 도 있어야 한다.

- 각 키에 해당하는 노드와 간선으로 연결된 인접 정점들을 값으로 넣어준다.

- 이때, 인접 정점이 2개 이상일 경우도 값으로 넣어야 하기 때문에 값의 자료형으로 리스트를 활용한다.

- 인접 정점으로는 부모 노드 또한 포함된다.

 

BFS, DFS 알고리즘을 구현해보자.

- BFS의 경우 2개의 큐 자료구조를 활용한다.

    - needVisit 큐(방문이 필요한 노드에 대한 정보를 가진 큐 - DFS 의 경우 스택으로 만든다.)

    - visited 큐(방문한 노드를 순서대로 적재한 큐 - 탐색이 끝나면 특정 노드를 어떤 순서에 방문했는지 알 수 있다.)

- 처음일 경우 needVisit 큐에 루트 노드(키 값) 에 대한 정보를 적재한다.(이번 트리에서는 A 가 해당된다.)

- needVisit 큐에 들어가 있는 데이터 중에서 가장 앞에 있는 정보(head) 를 꺼낸다.

- needVisit 큐에서 꺼낸 노드가 visited 큐에 있는지 검사한다.

- visited 큐에 없는 경우, 해당 노드를 visited 큐에 적재한다.(있는 경우 그냥 턴을 넘겨버린다.)

- 해당 노드가 visited 큐에 적재되고 나면 해당 노드에 간선으로 연결되어 있는 리스트에 적재되어 있는 인접 정점들을 왼쪽부터 순서대로 needVisit 큐에 적재한다.

- 위와 같은 순서로 프로세스가 진행되고 나면 한 턴 이 끝났다고 판단한다.

- 그 이후로는 위와 같은 과정을 반복한다.

 

* 각 알고리즘을 코드로 표현하면 아래와 같다.

- BFS.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		HashMap<String, List<String>> hashmap = new HashMap<String, List<String>>();
		
		List<String> list = new ArrayList<String>();
		
		list.add("B");
		list.add("C");
		hashmap.put("A", list);
		
		list = new ArrayList<String>();
		
		list.add("A");
		list.add("D");
		hashmap.put("B", list);
		
		list = new ArrayList<String>();
		
		list.add("A");
		list.add("G");
		list.add("H");
		list.add("I");
		hashmap.put("C", list);
		
		list = new ArrayList<String>();
		
		list.add("B");
		list.add("E");
		list.add("F");
		hashmap.put("D", list);
		
		list = new ArrayList<String>();
		
		list.add("D");
		hashmap.put("E", list);
		hashmap.put("F", list);
		
		list = new ArrayList<String>();
		
		list.add("C");
		hashmap.put("G", list);
		hashmap.put("H", list);
		
		list.add("J");
		hashmap.put("I", list);
		
		list = new ArrayList<String>();
		
		list.add("I");
		hashmap.put("J", list);
		
		bfs(hashmap, "A");
	}

	private static void bfs(HashMap<String, List<String>> hashmap, String startNode) {
		Queue<String> needVisit = new LinkedList<String>();
		Queue<String> visited = new LinkedList<String>();
		
		needVisit.offer(startNode);
		
		while(!needVisit.isEmpty()) {
			String node = needVisit.poll();
			if(!visited.contains(node)) {
				visited.offer(node);
				needVisit.addAll(hashmap.get(node));
			}
		}
		
		visited.stream().forEach(x -> System.out.print(x + " "));
		
	}
}

 

- DFS.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class DFS {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		HashMap<String, List<String>> hashmap = new HashMap<String, List<String>>();
		
		List<String> list = new ArrayList<String>();
		
		list.add("B");
		list.add("C");
		hashmap.put("A", list);
		
		list = new ArrayList<String>();
		
		list.add("A");
		list.add("D");
		hashmap.put("B", list);
		
		list = new ArrayList<String>();
		
		list.add("A");
		list.add("G");
		list.add("H");
		list.add("I");
		hashmap.put("C", list);
		
		list = new ArrayList<String>();
		
		list.add("B");
		list.add("E");
		list.add("F");
		hashmap.put("D", list);
		
		list = new ArrayList<String>();
		
		list.add("D");
		hashmap.put("E", list);
		hashmap.put("F", list);
		
		list = new ArrayList<String>();
		
		list.add("C");
		hashmap.put("G", list);
		hashmap.put("H", list);
		
		list.add("J");
		hashmap.put("I", list);
		
		list = new ArrayList<String>();
		
		list.add("I");
		hashmap.put("J", list);
		
		dfs(hashmap, "A");
	}

	private static void dfs(HashMap<String, List<String>> hashmap, String startNode) {
		Stack<String> needVisit = new Stack<String>();
		Queue<String> visited = new LinkedList<String>();
		
		needVisit.push(startNode);
		
		while(!needVisit.isEmpty()) {
			String node = needVisit.pop();
			if(!visited.contains(node)) {
				visited.offer(node);
				needVisit.addAll(hashmap.get(node));
			}
		}
		
		visited.stream().forEach(x -> System.out.print(x + " "));
		
	}
}

 

BFS, DFS 알고리즘의 시간 복잡도

- 노드 수 : V

- 간선 수 : E

- 위와 같이 작성된 코드에서 반복문은 V + E 번 만큼 수행한다.

- 시간 복잡도 : O(V + E)