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

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

  - 한 우물부터 깊이 판다.

  - 스택 이용

  Ex)

<hide/>
//깊이 우선 탐색 코드
	public static void SearchDepthFirst(Node node) {
		
		Stack<Node>  stack = new Stack<>();
		stack.push(node);
	
		while(!stack.empty()) {		// 스택이 비는 순간 끝
			Node next = stack.pop();
			System.out.println(next.data);	// 방문해서 출력
			for(Node child : next.children ) {
				stack.push(child);
			}
		}
	}

 

 

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

  - 여러 우물을 동시에 같은 깊이로

  - 큐를 이용한다.

  - 최단경로찾기에 적합하다.

  - 재귀적으로 이용하기 힘듦.

  Ex)

<hide/>
// 너비우선탐색코드
	public static void searchBreadthFirst(Node node) {
		
		Queue<Node> queue = new LinkedList<>();
		queue.add(node);
		
		while(!queue.isEmpty()) {
			Node next = queue.remove();
			for(Node child : next.children) {
				queue.add(child);	
			}	
		}		
	}

 

 

3. DFS와 BFS 비교

  - DFS: 자식부터 탐색/ 메모리 사용량이 적다. / 캐시 메모리에 적합 / 병렬처리에 적합 

  - BFS: 이웃부터 탐색/ 최소 깊이의 결과를 찾는다. / 깊이가 무한인 트리에도 사용가능