[Java] 알고리즘 - BFS, DFS 구현하기

1. DFS와 BFS

BFS란 Breadth First Search(너비우선탐색)이고 DFS는 Depth First Search(깊이우선탐색)이다. 이 둘은 그래프 자료구조에서 루트 노드에서 시작하여 완전 탐색을 수행하는 탐색 기법이다.

• DFS

DFS는 깊이 우선 탐색으로, 한 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 검색 속도 자체는 BFS에 비해 느리지만 조금 더 간단하다. 스택 혹은 재귀함수를 이용하여 구현한다.

• BFS

BFS는 너비 우선 탐색으로, 아래 그림과 같이 루트 노드에서 탐색을 시작하여 같은 레벨에 있는 노드를 모두 탐색한 다음 하위 레벨로 내려가 또 모두 탐색을 진행하다가, 더이상 탐색할 노드가 없을 때 탐색을 멈추는 방식으로 동작한다. 큐를 이용하여 구현한다.

2. Java에서 DFS와 BFS의 구현

• DFS의 Java구현

DFS는 스택과 재귀함수를 통해 구현할 수 있지만 일반적으로 재귀함수를 통하여 구현한다.

class Graph {
	private int V;
	private LinkedList<Integer> adj[]; // 링크드리스트의 배열
	
	// constructor
	Graph (int v) {
		V = v;
		adj = new LinkedList[v];
		// v개의 LinkedList 선언 및 생성
		for (int i = 0; i < v; ++i) {
			adj[i] = new LinkedList(); 
		}
	}
	void addEdge (int v, int w) { // v번째 LinkedList 에 w를 삽입
		adj[v].add(w); 
	}
	// DFS 함수
	void DFS(int v) { // v를 시작노드로!
		boolean visited[] = new boolean[V]; // 각 노드이 방문 여부를 저장하기 위해
		DFSUtil(v, visited);
	}
	// DFS에서 호출되는 함수
	void DFSUtil(int v, boolean visited[])  {
		// 현재 노드를 방문한 것으로 체크 (visited의 v번째 요소를 true로)
		visited[v] = true;
		System.out.println(v + " ");
		
		// 방문한 노드와 인접한 모든 노드를 가지고 온다
		Iterator<Integer> it = adj[v].listIterator();
		while (it.hasNext()) {
			int n = it.next();
			// 방문하지 않은 노드면 해당 노드를 다시 시작 노드로하여 DFSUtil을 호출
			if (!visited[n])
				DFSUtil(n, visited); // 재귀호출!
		}
	}
}

• BFS의 Java구현

  BFS는 일반적으로 Queue를 이용하여 구현한다.

class Graph {
	private int V;
	private LinkedList<Integer> adj[]; // 링크드리스트의 배열
	
	// constructor
	Graph (int v) {
		V = v;
		adj = new LinkedList[v];
		// v개의 LinkedList 선언 및 생성
		for (int i = 0; i < v; ++i) {
			adj[i] = new LinkedList(); 
		}
	}
	void addEdge (int v, int w) { // v번째 LinkedList 에 w를 삽입
		adj[v].add(w); 
	}
	// DFS 함수
	void BFS(int s) {
		boolean visited[] = new boolean[V]; // 각 노드이 방문 여부를 저장하기 위해
		LinkedList<Integer> queue = new LinkedList<Integer>();
		
		visited[s] = true;
		queue.add(s);
		
		while (queue.size() != 0) {
			// 방문한 노드를 큐에서 추출하고 값을 출력
			s = queue.poll();
			System.out.println(s + " ");
			
			// 방문한 노드와 인접한 모든 노드를 가져온다.
			Itertor<Integer> i = adj[s].listIterator();
			while (i.hasNext()) {
				int n = i.next();
				// 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입
				if (!visited[n]) {
					visited[n] = true;
					queue.add();
				}
			}
		}
	}
}

3. DFS, BFS를 활용하면 좋은 상황

DFS와 BFS를 활용하면 좋은 상황으로는 아래와 같은 상황들이 있다.

(1) 그래프의 모든 정점을 방문하는 것이 주요한 문제: DFS, BFS 모두 무방하다.

(2) 경로의 특징을 저장해둬야 하는 문제: 각 장점에 숫자가 있고 a 부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 하는 경우는 DFS를 사용해야 한다. BFS는 경로의 특징을 저장하지 못한다.

(3) 최단거리를 구하는 문제: BFS가 유리하다. DFS의 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만 BFS의 경우 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.

Reference

​https://devuna.tistory.com/32