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

  깊이 우선 탐색(DFS)란?

Depth First Search의 약자
한 방향으로 갈 수 있을 때 까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 그래프탐색 방법으로 넓게 보다는 깊게 탐색하는 방법

• 자기 자신을 다시 호출 하는 순환 알고리즘의 형태를 가지고 있다.
• 넓게(wid) 보다는 깊게(deep) 탐색하는 것
• 모든 노드를 방문하고자 하는 경우 선택한다
• 전위 순회(Pre-order Traversals)를 포함한 다른 트리 순회는 모두 DFS의 한 종류이다
• 그래프 탐색 시 노드의 방문여부를 반드시 검사하여야 한다
  → 검사를 하지 않을 경우 무한루프

 

  깊이 우선 탐색(DFS)의 과정

  DFS 구현

DFS를 구현하는 방법은 1.순환 호출 이용  2.스택 이용  의 두가지 방법이 있다.
인접행렬과 인접리스트를 이용하여 각각 구현해 보면 다음과 같다.

1. 인접행렬

구현1 순환 호출 이용

import java.util.Scanner;

class Dfs {
	static int vertex;
	static int map[][];
	static int visit[];

	static void depthFirstSearch(int v) {
		visit[v] = 1;
		for (int i = 1; i <= vertex; i++)// 시작노드에 인접한 노드 탐색
		{
			if (map[v][i] == 1 && visit[i] == 0)// (현재 지점에서 방문할 곳이 계속 있다면
			{
				System.out.printf("%d ", i);
				depthFirstSearch(i); // 다시 탐색
			}
		}
	}

	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();// 테스트 케이스 개수

		for (int test_case = 1; test_case <= T; test_case++) {
			vertex = sc.nextInt(); // 정점의 개수
			int start = sc.nextInt(); // 시작노드

			map = new int[vertex + 1][vertex + 1]; // 인접행렬
			visit = new int[vertex + 1];

			while (true)// 연결된 두 노드 입력
			{
				int v1 = sc.nextInt();
				int v2 = sc.nextInt();
				if (v1 == -1 && v2 == -1) {
					break;
				}
				map[v1][v2] = map[v2][v1] = 1;
			}
			System.out.printf("#%d ", test_case);
			System.out.printf("%d ", start);
			depthFirstSearch(start);
			System.out.printf("\n");
		}
		sc.close();
	}
}

 

<실행 결과>

 

구현2 스택 이용
(추가 예정...)

 

  Reference

• https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html 
• https://swexpertacademy.com/main/code/referenceCode/referenceCodeDetail.do?referenceId=DFS_SEARCHING&category=undefined