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

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

 

그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

기능	특징	시간 복잡도(노드 수 : V, 에지 수 : E)
그래프 완전 탐색	재귀함수, Stack(LIFO) 사용	O(V+E)

 

DFS 원리

1. 시작할 노드를 정한 후 사용할 자료구조 초기화
2. Stack에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입
3. Stack 자료구조에 값이 없을 때까지 반복

 

 

 

DFS 구현 방법 두 가지

재귀

1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 

 

스택

1 -> 3 -> 4 -> 6 -> 2 -> 5 -> 

 

* 재귀의 경우 오름차순 기준으로 해서 위의 탐색 순서가 나왔지만, 기준이나 구현 방법에 따라서 탐색 순서는 바뀔 수 있습니다.

 

코드

Java 재귀

package com.java.coding;

public class DFSExam {
	// 방문처리에 사용 할 배열선언
	public static boolean[] vistied = new boolean[9];
	
	// 1. 자료 구조 초기화
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	public static int[][] graph = {{},
								{2,3}, // 1노드의 인접노드
								{5,6}, // 2
								{4},  // 3
								{6},  // 4
								{},  // 5
								{}};  // 6
	
	public static void main(String[] args) {
		// 2. dfs 호출
		dfs(1);
	}
	
	public static void dfs(int nodeIndex) {
		// 3. 노드 방문 처리 및 방문여부 체크하여 재귀
		// 방문 처리
		vistied[nodeIndex] = true;
		// 방문 노드 출력
		System.out.print(nodeIndex + " -> ");
		// 방문한 노드에 인접한 노드 찾기
		for (int node : graph[nodeIndex]) {
			// 인접한 노드가 방문한 적이 없다면 DFS 수행
			if(!vistied[node]) {
				// 재귀
				dfs(node);
			}
		}
	}
}

Java Stack

package com.java.coding;

import java.util.Stack;

public class DFSStackExam {

	
	// 1. 자료구조 초기화
	// 방문처리에 사용 할 배열선언
	public static boolean[] vistied = new boolean[9];
	
	public static int[][] graph = {{},
								{2,3}, // 1노드의 인접노드
								{5,6}, // 2
								{4},  // 3
								{6},  // 4
								{},  // 5
								{}};  // 6
	// DFS 사용 할 스택
	static Stack<Integer> stack = new Stack<>();
	
	public static void main(String[] args) {
		
		// 2. Stack의 시작노드부터 
		// 시작 노드를 스택에 넣어줍니다.
		stack.push(1);
		// 시작 노드 방문처리
		vistied[1] = true;
		
		// 3. 스택에 값이 없을 때까지 반복
		while(!stack.isEmpty()) {
			
			// 스택에서 하나를 꺼냅니다.
			int nodeIndex = stack.pop();
			
			// 방문 노드 출력
			System.out.print(nodeIndex + " -> ");
			
			// 4. 인접 노드 방문여부 에 따라 처리
			// 꺼낸 노드와 인접한 노드 찾기
			for (int LinkedNode : graph[nodeIndex]) {
				// 인접한 노드를 방문하지 않았을 경우에 스택에 넣고 방문처리 
				if(!vistied[LinkedNode]) {
					stack.push(LinkedNode);
					vistied[LinkedNode] = true;
				}
			}
		}
	}
}