깊이 우선 탐색 Depth-first search

깊이 우선 탐색

시작 노드와 직접 연관된 하위 노드 끝까지 모두 탐색한 후 다음 하위 노드를 탐색하는 방법

일단 경로 하나의 모든 층을 탐색한 후 그 다음 경로의 모든 층을 탐색하는 방법

재귀나 스택을 이용해 구현

 

백트래킹

문제의 해답을 찾지 못했을 때 이전 단계로 돌아가는 것

자식노드에서 값을 찾지 못했을 때 부모노드로 돌아가는 것

 

슈도코드

DFS(그래프, 시작 정점) { 

   시작점 방문여부 = true

      for ( 시작점과 연결된 정점 탐색 ){

            if (탐색 정점의 방문여부 == false){

                탐색 정점의 방문여부 = true            

                DFS(그래프, 탐색 정점) //재귀              

         }

     }   

}

시간복잡도

초기화 시간 : Ο(노드갯수)

그래프 탐색 시간 :  Ο(노드갯수 + 간선갯수)

• 정점은 최대 1번 탐색한다.
• 간선은 최대 2번 탐색한다.

 

전체 수행시간 

Ο( N + E )

 

구현 JAVA

package algorithm;

import java.util.*;

public class dfs {
	
	static StringBuilder route = new StringBuilder(); //경로 방문순서
	
	public static void main(String[] args) {
		//인접리스트를 이용하여 그래프 구현 
		int[][] graph = { {},
				{ 2, 3, 4 },
				{ 5, 6 },
				{ 7 },
				{ 8 },
				{},
				{ 9 },
				{},
				{},
				{} };
		//정점의 방문여부(정점의 상태)를 저장할 배열
		boolean[] visited = new boolean[10];
		
        	//깊이 탐색 실행
		dfs f = new dfs();
		f.dfs(graph, visited, 1);
		
        	//경로 방문 순서 출력
		System.out.println(route.toString());
		
	}

	public void dfs(int[][] graph, boolean[] visited, int start) {
		//경로 탐색
		for(int v : graph[start]) {
			//정점의 상태가 미방문 false이면 탐색
			if(!visited[v]) {
				visited[v] = true;												
				route.append(v); //방문한 경로 저장	
				dfs(graph, visited, v); //재귀
			}				
		}			
	};
}

25693748

 

구현 JAVA

0에서 9로 가는 최단 경로 구하기 

 

package algorithm;

import java.util.*;

public class dfs {
	
	static StringBuilder route = new StringBuilder(); //경로 방문순서
	
	public static void main(String[] args) {
		//인접리스트를 이용하여 그래프 구현 
		int[][] graph = { {},
						  { 2, 3, 4 },
						  { 5, 6 },
						  { 7 },
						  { 8 },
						  {},
						  { 9 },
						  {},
						  {},
						  {} };
		//정점의 방문여부(정점의 상태)를 저장할 배열
		boolean[] visited = new boolean[10];
		
		
		
		dfs f = new dfs();
		f.dfs(graph, visited, 1);
		
		
	}

	public void dfs(int[][] graph, boolean[] visited, int start) {
		
		if(start == graph.length-1) {
			System.out.println(route.toString());
		}
		//경로 탐색
		for(int v : graph[start]) {
			//정점의 상태가 미방문 false이면 탐색
			if(!visited[v]) {
				visited[v] = true;												
				route.append(v); //방문한 경로 저장	
				dfs(graph, visited, v);
				//백트래킹
				visited[v] = false;
				route.deleteCharAt(route.length() - 1);
			}				
		}			
	}
}

 

269

출처

Depth First Search (DFS), www.programiz.com

컴퓨터 알고리즘 기초 15강 깊이 우선 탐색, T아카데미

코드 없는 알고리즘과 데이터 구조, 암스트롱 수베로