[JAVA] 탐색 알고리즘 DFS (Depth-First Search, 깊이 우선 탐색)

DFS

DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며,

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다.

 

그래프의 기본 구조를 먼저 알아 보겠습니다.

그래프는 노드(Node) 와 간선(Edge)로 표현되며, 이때 노드를 정점(Vertex)라고 말합니다.

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말합니다.

 

DFS의 수행과정은 다음과 같습니다.

 

그림 1

위와 같은 그래프에서, 노드1이 시작 노드라고 하였을때,

1-2-7-6순으로 갑니다. 6번노드에서는 더이상 갈 곳이 없는데,

이 때에는 자신을 호출한 부모노드로 돌아갑니다(backtracking).

7번 노드로 돌아가고, 다시 7번노드에서 방문한 적이 없는 8번 노드로 가게 됩니다.

 

8번노드에서는 인접한 노드중 방문하지 않은 노드가 없으므로 backgracking을 합니다.

8-7-2-1 번으로 돌아가고, 다시 1번 노드에서 3번노드로 순서가 향하게 됩니다.

 

따라서 위의 그래프의 순서는 1-2-7-6-8-3-4-5 입니다. 

 

※ 인접한 노드중에서 방문하지 않은 노드가 여러개 있으면 번호가 낮은 순서부터 처리합니다.

 

 

 

DFS 구현 방법

DFS 구현방법에는 재귀함수와 스택 두가지가 있습니다. 하나씩 알아가 봅시다.

구현에 있어서, 인접행렬 또는 인접리스트를 통해 구현할 수 있습니다.

 

인접행렬은 정점(V)이 n개일 때 N*N 이차원 배열로 나타낼 수 있습니다.

 

(1) 재귀함수

그림 1

위의 그림1번 그래프로 구현해 보겠습니다.

import java.util.Scanner;

public class DFSRecursion {
	
	public static void dfs(int[][]a, boolean[]visit,int v) {
		int n = a.length-1;  ///(0,0)행,열을 제외한 길이
		
		visit[v]=true; ///v노드를 방문처리
		System.out.print(v+" "); //v노드 출력
		
		for (int i = 1; i <= n; i++) {
			if(a[v][i]==1&&!visit[i]) {///노드v와 인접한 노드이고, 그 노드가 방문된 적이 없다면
				dfs(a,visit,i);
				
			}
		}
		
	}
		
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V= 8; //정점
		int E = 9; //간선
		boolean[] c = new boolean[V+1]; ///노드 1부터 시작하기 위해
		int[][] a = new int[V+1][V+1];  ///(0,0)부터 시작
		
		for (int i = 0; i < E; i++) {
			int v1= sc.nextInt();
			int v2 = sc.nextInt();
			
			a[v1][v2]=1;
			a[v2][v1]=1;
		}
		
		dfs(a,c,1);
		
		
	}
}

 

 

 

(2) 스택(Stack)

 

import java.util.Scanner;
import java.util.Stack;

public class DFSStack {
	
	public static void dfs(int[][]a, boolean[]visit,int v) {
		Stack<Integer> stack = new Stack<>();
		
		stack.push(v);
//		visit[v]= true;
//		System.out.println(v+" ");
		
		while(!stack.empty()) {
			int curr=stack.pop();
			
			if(visit[curr])continue;
			
			visit[curr]= true;
			System.out.print(curr+" ");

			for(int i= a.length-1;i>=1;i--) {
				if(!visit[i]&&a[curr][i]!=0) {
					stack.push(i);
					
				}
			}
		}
	}
		
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V= 8; //정점
		int E = 9; //간선
		boolean[] c = new boolean[V+1]; ///노드 1부터 시작하기 위해
		int[][] a = new int[V+1][V+1];  ///(0,0)부터 시작
		
		for (int i = 0; i < E; i++) {
			int v1= sc.nextInt();
			int v2 = sc.nextInt();
			
			a[v1][v2]=1;
			a[v2][v1]=1;
		}
		
		dfs(a,c,1);
		
		
	}
}

---

DFS ... 조금더 공부를 해야할거같습니다.