[Algorithm] 깊이 우선 탐색 알고리즘(JAVA 구현)

-깊이 우선 탐색(DFS)이란?

그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. 그중 깊이 우선 탐색은 아래와 같은 순서를 따른다.

시작 정점(V)을 방문한다.
V에 인접한 정점들 중 방문하지 않은 정점을 방문하며 스택(Stack)에 삽입한다.
인접한 정점이 없는 정점까지 2번을 반복한다. 이후 인접한 정점이 없는 경우 다시 스택에서 pop() 후 2~3번을 반복한다.

즉 깊이 우선 탐색의 경우에는 인접한 정점이 없는 정점에 도달할 때까지 인접한 정점을 반복해서 방문하며 Stack에 넣는 작업을 한다. 깊이 우선 탐색의 구현에 사용되는 자료구조는 1) 각 노드에 방문여부를 표시할 배열, 2) 정점의 저장을 위한 스택 정도가 될 수 있다. 물론 추가적으로 그래프의 구현을 위한 작업이 필요할 수 있지만, 여기선 ArrayList를 활용하여 인접 노드를 단순히 표현하도록 하겠다.

너비 우선 탐색과의 큰 차이점은 인접한 정점을 우선적으로 방문한다는 점이다. 이에 반해 너비 우선 탐색은 인접한 정점을 모두 방문한 후, 다음 정점으로 이동한다는 차이점이 존재한다.

기본적인 코드는 BFS와 유사하며 일부분만 바꿔주면 된다.

import java.util.ArrayList;
import java.util.LinkedList;


public class DFS {
	static int arr[] = new int[8];
	static ArrayList<int[]> arrayList =  new ArrayList<int[]>();
	public static void dfs(int start) { // Stack을 사용하지 않고 컴퓨터 시스템의 기본인 스텍프레임을 이용하므로 재귀함수 만으로 구현가능
		if(arr[start] ==1) return; // 재귀 호출을 통해 들어온 정점이 이미 방문한 노드라면 종료
		arr[start] = 1; //방문하지 않았다면 방문처리
		
		System.out.println(start); // Output
		
		for(int i =0;i<arrayList.get(start).length;i++) { // 인접한 정점의 수 만큼 반복
			int y = arrayList.get(start)[i];
			dfs(y); // 인접한 정점을 만나면 바로 재귀호출을 수행한다.
		}
	}

	public static void main(String[] args) {
		arrayList.add(0,new int[] {0});
		arrayList.add(1,new int[] {2,3});
		arrayList.add(2,new int[] {1,3,4,5});
		arrayList.add(3,new int[] {1,2,6,7});
		arrayList.add(4,new int[] {2,5});
		arrayList.add(5,new int[] {2,4});
		arrayList.add(6,new int[] {3,7});
		arrayList.add(7,new int[] {3,6});
		
		dfs(1);
		
	}

}

이것의 출력 결과로는 1,2,3,6,7,4,5 순으로 정점을 방문한다는 것을 알 수 있다.

저작자표시 (새창열림)

-깊이 우선 탐색(DFS)이란?

티스토리툴바