[JAVA] 깊이 우선 탐색 DFS(Depth-First Search)

 

 

동작방식

맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식입니다.

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

시간복잡도

- 인접리스트 : O(|V| + |E|) (정점의 개수:V, 간선의 개수:E)

- 인접행렬 : O(V^2) (정점의 개수:V)

참고사이트

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

기본코드

입력값

7 8 1 2 1 3 2 4 2 5 3 7 4 6 5 6 6 7

코드

package study.graph;


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class DFS {
	static int[] used;
	static int[][] map;
	static int N, M;
	public static void main(String[] args) throws IOException{
		
		System.setIn(new FileInputStream("input\\dfs.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		used = new int[N+1];
		map = new int[N+1][N+1]; // 인접행렬을 이용하기 위한 2차원 배열 생성
		
		StringTokenizer st = null;
		for(int m=0; m<M; m++) {
			st = new  StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			map[a][b] = 1;
			map[b][a] = 1; //양방향이기 때문에..
		}
		
		System.out.print("그래프 DFS 방문 순서 : " );
		dfs(1);
		
		bw.close();
		br.close();
	}
	
	static void dfs(int point) {
		Stack<Integer> st = new Stack<Integer>();
		st.add(point);
		used[point] = 1; // 방문표시
		System.out.print( point + " ");
		
		while(!st.isEmpty()) {
			st.pop();
			for(int i=1; i<=N; i++) {
				if(map[point][i]==1 && used[i] == 0) {
					// 다음 노드와 연결되어 있고 아직 방문하지 않았으면 st에 넣고, 재귀실행
					st.add(i);
					used[i] = 1;
					dfs(i);
				}
			}
		}
		
	}
}