DFS

 

 

 

Depth First Search. 깊이 우선 탐색이다.

 

BFS와 마찬가지로 그래프 자료구조를 탐색할 때 사용하는 알고리즘이다.

 

 

 

BFS와는 달리 DFS는 정점의 자식을 먼저 탐색한다.

 

 

BFS에서는 두 개의 큐 자료구조를 사용해서 구현했지만, DFS에서는 BFS에서 탐색해야 하는 부분을 저장하는 큐 (needvisit)를 스택으로 바꿔서 활용한다.

 

 

BFS의 로직과 DFS의 로직을 비교해서 공부해보자.

 

 

 

import java.util.*;
import java.io.*;

public class Main {
    public ArrayList<String> dfsFunc(HashMap<String, ArrayList<String>> graph, String startNode) {
        ArrayList<String> visited = new ArrayList<String>();
        Stack<String> needVisit = new Stack<String>(); // BFS에서는 큐 대신 스택을 사용한다.
        
        needVisit.add(startNode);
        
        while (needVisit.size() > 0) {
            String node = needVisit.pop(); 
            if (!visited.contains(node)) {
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }
        return visited;
    }
}

 

 

시간복잡도 : O(V+E)