1. 개념

최근의 주변 정점을 우선으로 방문하는 탐색 방법

• 한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하며 탐색함
• 정점을 방문할 때마다 인접한 정점 중 한 곳을 따라 우선 탐색을 진행하다가, 정점이 없어서 더 이상 진행을 할 수 없을 경우 거꾸로 되돌아가면서 아직 탐색하지 않은 인접한 정점을 방문함
• 재귀함수 또는 스택을 통해 구현함

2. 구현

2-1. 재귀

import java.util.LinkedList;

public class DFSResursive {
	private static class Graph {
      private final int vertex;	// 정점 수
      private final LinkedList<Integer>[] adjVertices;	// 인접 리스트
      
      /**
       * 생성자
       * - 정점의 수를 받아 adjVertices 배열 초기화
       */
      public Graph(int vertex) {
      	this.vertex = vertex;
        adjVertices = new LinkedList[vertex];
        for(int index = 0; index < vertex; ++index) {
        	adjVertices[index] = new LinkedList();
        }
      }

      /**
       * 주어진 두 정점 사이에 간선을 추가하는 메서드
       */
      public void addEdge(int vertex, int dest) {
          adjVertices[vertex].add(dest);
      }

      /**
       * DFS를 수행하는 메서드
       * - 방문하지 않은 정점을 시작점으로 DFSUtil 메서드 호출
       * - visited 배열 초기화 및 탐색 시작
       */
      public void DFS(int start) {
      	// 방문하지 않은 모든 정점 표시
      	boolean[] visited = new boolean[vertex];

        // DFS 수행을 위한 DFSUtil 메서드 재귀 호출
        DFSUtil(start, visited);
      }
      
      /**
       * DFS에서 사용하는 메서드
       * - 주어진 정점을 방문하고, 인접한 정점들을 재귀적으로 방문
       * - visited 배열을 사용하여 이미 방문한 정점을 다시 방문하지 않도록 함
       */
      public void DFSUtil(int vertex, boolean[] visited) {
          // 주어진 정점을 방문한 정점으로 표시
          visited[vertex] = true;

          // 해당 정점에 인접한 모든 정점에 대해 반복 호출
          for(int adj : adjVertices[number]) {
          	if (!visited[adj]) {
            	DFSUtil(adj, visited);
            }
          }
      }
    }
    
    public static void main(String args[]) {
    	Graph graph = new Graph(4);
        
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        
        // 정점 2를 시작으로 DFS 수행
        graph.DFS(2);
	}
}

2-2. 스택

import java.util.LinkedList;
import java.util.Stack;

public class DFSStack {
	private static class Graph {
      private final int vertex;
      private final LinkedList<Integer>[] adjVertices;

      public Graph(int vertex) {
      	this.vertex = vertex;
        adjVertices = new LinkedList[vertex];
        for(int index = 0; index < vertex; ++index) {
        	adjVertices[index] = new LinkedList();
        }
      }

      public void addEdge(int vertex, int dest) {
          adjVertices[vertex].add(dest);
      }

      /**
       * DFS를 수행하는 메서드
       * - 명시적인 스택을 사용하여 반복문으로 정점 방문
       * - visited 배열로 방문 여부 체크
       */
      public void DFS(int start) {
      	boolean[] visited = new boolean[vertex];
        
        // DFS 수행에 사용할 스택 초기화
        Stack<Integer> stack = new Stack<>();
        
        // 시작 정점을 스택에 추가
        stack.push(start);
        
        // 스택에 정점이 존재하는 동안 반복(모든 정점을 방문하면 스택이 비게 됨)
        while(!stack.isEmpty()) {
        	// 스택의 맨 위 정점을 꺼냄
        	int vertex = stack.pop();
            
            // 해당 정점을 방문하지 않은 경우만 처리
            if(!visited[vertex]) {
            	// 주어진 정점을 방문한 정점으로 표시
            	visited[vertex] = true;
                
                // 현재 정점의 모든 인접 정점 확인
                for(int adj : adjList[vertex]) {
                	// 인접 정점을 아직 방문하지 않은 경우
                	if(!visited[adj]) {
                    	// 해당 인접 정점을 스택에 추가
                    	stack.push(adj);
                    }
                }
            }
        }
      }
    }
    
    public static void main(String args[]) {
    	Graph graph = new Graph(4);
        
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        graph.DFS(2);
	}
}

3. 성능 분석

표현	성능	비고
인접 리스트	O(|V|+|E|)	V : 정점, E : 간선
인접 행렬	O(|V|^2)	상동

• 하나의 스택을 사용하고 있으며, 이는 입력 정점의 개수에 비례함
• 모든 정점의 인접한 정점을 다루는 것은 간선의 개수에 비례함

4. 특징

• 그래프 알고리즘이다.
• 모든 경로를 방문해야 하는 경우에 사용하기 적합하다.

---

📖 참고

• 이관용, 김진욱(2024). 알고리즘. 한국방송통신대학교출판문화원
• DFS & BFS