[JAVA] DFS 구현하기

DFS 정의

DFS는 Depth-First Search 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

DFS 동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

DFS 어떨 때 사용할까?

주로 모든 노드를 방문하고자 하는 경우에 사용한다.
대표적으로
미로 찾기
그래프의 위상 정렬
모든 경우 다 해보기(전체 탐색)
연결 구성 요소 찾기
이분 그래프
[참고]
https://coding-grandpa.tistory.com/122

DFS 장/단점

**DFS의 장점**
DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
DFS를 사용하여 그래프에서 순환을 감지할 수 있다. 

**DFS의 단점**
순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
DFS는 두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 가장 좋은 알고리즘이 아닐 수 있다.

DFS 구현방법

1. stack
2. 재귀

1. stack을 사용한 DFS 구현

package Graph;
import java.util.*;

public class DFS {
	
	static ArrayList<Integer>[] adjList;
	static int[][] adjMatrix;
	static int N;
	static boolean[] visited;
	static Stack<Integer> stk;
	
	static void addEdgeToAdjList(int v , int w) {	
		adjList[v].add(w);
		adjList[w].add(v);
	}
	
	static void addEdgeToAdjMatrix(int v , int w) {	
		adjMatrix[v][w] = 1;
		adjMatrix[w][v] = 1;
	}
	
	static void initAdjList() {
		
		adjList = new ArrayList[N + 1];  // 배열 생성
		visited = new boolean[N+1];
		for (int i = 0; i < N+1; i++) {
		    adjList[i] = new ArrayList<Integer>();  // 각 요소 초기화
		}
	}
	
	static void initAdjMatrix() {
		
		adjMatrix = new int[N+1][N+1];
		visited = new boolean[N+1];
		
	}
	
	static void dfsByAdjList(int startNode) {
		stk = new Stack<>();
		//시작 점 스택에 넣어주기
		stk.push(startNode);
		visited[startNode] = true;

		
		//스택이 비어있지 않다면 연결노드를 방문한다.
		while(!stk.isEmpty()) {
			
			//스택에허 하나 꺼낸다.
			startNode = stk.pop();
			System.out.println(startNode);
			//인접 노드들 찾기.
			for(int linkedNode : adjList[startNode]) {
				
				//방문하지 않았다면.
				if(!visited[linkedNode]) {
					//스택에 넣어주고
					stk.push(linkedNode);
					// 방문처리를 해준다.
					visited[linkedNode] = true;
				}
			}	
		}
	}
	
	static void dfsByAdjMatrix(int startNode) {
		stk = new Stack<>();
		//시작 점 스택에 넣어주기
		stk.push(startNode);
		visited[startNode] = true;

		//스택이 비어있지 않다면 연결노드를 방문한다.
		while(!stk.isEmpty()) {			
			//스택에허 하나 꺼낸다.
			startNode = stk.pop();
			System.out.println(startNode);
			//인접 노드들 찾기.
			for(int linkedNode = 0; linkedNode<adjMatrix[startNode].length; linkedNode++) {
				
				//방문하지 않았다면.
				if(!visited[linkedNode]&&adjMatrix[startNode][linkedNode] == 1) {
					//스택에 넣어주고
					stk.push(linkedNode);
					// 방문처리를 해준다.
					visited[linkedNode] = true;
				}
			}	
		}
	}
	
	public static void main(String [] args) {
		
		//정점의 갯수;
		N = 8;
		
		//인접 리스트를 이용한 DFS
		initAdjList();
		//간선 추가하기
		addEdgeToAdjList(1,2);
		addEdgeToAdjList(1,3);
		addEdgeToAdjList(1,8);
		addEdgeToAdjList(2,7);
		addEdgeToAdjList(7,8);
		addEdgeToAdjList(7,6);
		addEdgeToAdjList(3,4);
		addEdgeToAdjList(3,5);		
		dfsByAdjList(1);
		
		//인접 행렬을 이용한 DFS
		initAdjMatrix();
		//간선 추가하기
		addEdgeToAdjMatrix(1,2);
		addEdgeToAdjMatrix(1,3);
		addEdgeToAdjMatrix(1,8);
		addEdgeToAdjMatrix(2,7);
		addEdgeToAdjMatrix(7,8);
		addEdgeToAdjMatrix(7,6);
		addEdgeToAdjMatrix(3,4);
		addEdgeToAdjMatrix(3,5);		
		dfsByAdjMatrix(1);
		
	}
}

출력값

1
8
7
6
3
5
4
2

2. 재귀 사용한 DFS 구현

import java.util.*;

public class DfsByRecursive {
	
	static ArrayList<Integer>[] adjList;
	static int N;
	static boolean[] visited;
	
	static void addEdgeToAdjList(int v , int w) {	
		adjList[v].add(w);
		adjList[w].add(v);
	}
	

	static void initAdjList() {
		
		adjList = new ArrayList[N + 1];  // 배열 생성
		visited = new boolean[N+1];
		for (int i = 0; i < N+1; i++) {
		    adjList[i] = new ArrayList<Integer>();  // 각 요소 초기화
		}
	}

	static void dfs(int startNode) {
		
		visited[startNode] = true;
		System.out.println(startNode);
		
		for(int linkedNode : adjList[startNode]) {
			if(!visited[linkedNode]) {
				dfs(linkedNode);
			}
			
		}
		
	}
	public static void main(String [] args) {
		
		//정점의 갯수;
		N = 8;
		
		//인접 리스트를 이용한 DFS
		initAdjList();
		//간선 추가하기
		addEdgeToAdjList(1,2);
		addEdgeToAdjList(1,3);
		addEdgeToAdjList(1,8);
		addEdgeToAdjList(2,7);
		addEdgeToAdjList(7,8);
		addEdgeToAdjList(7,6);
		addEdgeToAdjList(3,4);
		addEdgeToAdjList(3,5);		
		//dfsByAdjList(1);
	
		dfs(1);
	}
}

DFS 구현 stack VS 재귀?

재귀 함수
그래프의 깊이가 깊지 않고, 코드의 간결함과 직관성을 중시할 때 사용하기 좋다.

스택 사용
그래프의 깊이가 매우 깊거나 대규모 그래프를 다룰 때, 스택 오버플로우를 방지해야 하는 경우에 더 적합하다.

∴ 일반적으로는 재귀 방식이 더 간단하고 직관적이지만, 그래프의 크기와 깊이에 따라 스택 방식이 더 안정적일 수 있다.

DFS 구현시 인접행렬 VS 인접리스트?

인접 리스트
메모리 효율이 중요하고, 그래프의 간선이 적거나 정점의 수가 많을 때 적합합니다.
-> 그래프의 밀도가 낮을 때 (즉, 간선이 적을 때)
: 인접 리스트는 각 정점에 대해 연결된 정점들만저장하므로, 그래프의 간선이 적을 때 메모리를 절약할 수 있다
-> 정점의 수가 매우 많고, 간선의 수가 적을 때
수천개의 정점이 있지만, 각 정점에 연결된 간선이 몇개 안된다면 인접 리스트가 적합하다. 이 경우 인접 행렬은 너무 많은 불필요한 0 값을 저장하게 되기 때문이다.

인접 행렬
그래프가 조밀하고, 정점 간 연결 여부를 빠르게 확인해야 할 때 적합합니다.
-> 그래프의 밀도가 높을 때 (즉, 간선이 많을 때)
: 인접 행렬은 모든 정점 쌍에 대해 간선이 존재하는지 여부를 저장하기 때문에, 간선이 많을 때 효율적으로 활용할 수 있다. 완전 그래프처럼 간선이 많이 연결된 경우 인접 행렬이 더 적합하다.
-> 정점의 수가 적고, 간선의 수가 많은 경우
: 만약 정점의 개수가 적고 모든 정점이 서로 많이 연결되어 있다면, 인접 행렬이 적합하다. 이 경우 인접리스트는 오히려 비효율적일 수 있다.