[자료구조] DFS & BFS

깊이우선탐색 - DFS

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 → 정점의 자식들을 먼저 탐색하는 방식
• 스택
• 자기 자신을 호출하는 순환 알고리즘의 형태를 지님
• 인접리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

public class DFS {
    public static void main(String[] args) {
        HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();
        graph.put("A", new ArrayList<String>(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList<String>(Arrays.asList("A", "D")));
        graph.put("C", new ArrayList<String>(Arrays.asList("A", "G", "H", "I")));
        graph.put("D", new ArrayList<String>(Arrays.asList("B", "E", "F")));
        graph.put("E", new ArrayList<String>(Arrays.asList("D")));
        graph.put("F", new ArrayList<String>(Arrays.asList("D")));
        graph.put("G", new ArrayList<String>(Arrays.asList("C")));
        graph.put("H", new ArrayList<String>(Arrays.asList("C")));
        graph.put("I", new ArrayList<String>(Arrays.asList("C", "J")));
        graph.put("J", new ArrayList<String>(Arrays.asList("I")));
 
        System.out.println(dfsFunc(graph, "A"));
    }
 
    private static ArrayList<String> dfsFunc(HashMap<String, ArrayList<String>> graph, String startNode){
        ArrayList<String> visited = new ArrayList<String>();
        ArrayList<String> needVisit = new ArrayList<String>();
 
        needVisit.add(startNode);
 
        while(needVisit.size() > 0){
            //BFS와 다르게 DFS는 스택 구조이다.
            String node = needVisit.remove(needVisit.size() - 1);
 
            if(!visited.contains(node)){
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }
 
        return visited;
    }
}

• A - C - I - J - H - G - B - D - F - E

---

너비우선탐색 - BFS

• 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
• 재귀적으로 동작 X
• 선입 선출
• 큐

public class BFS {
    public static void main(String[] args) {
        HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();
 
        graph.put("A", new ArrayList<String>(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList<String>(Arrays.asList("A", "D")));
        graph.put("C", new ArrayList<String>(Arrays.asList("A", "G", "H", "I")));
        graph.put("D", new ArrayList<String>(Arrays.asList("B", "E", "F")));
        graph.put("E", new ArrayList<String>(Arrays.asList("D")));
        graph.put("F", new ArrayList<String>(Arrays.asList("D")));
        graph.put("G", new ArrayList<String>(Arrays.asList("C")));
        graph.put("H", new ArrayList<String>(Arrays.asList("C")));
        graph.put("I", new ArrayList<String>(Arrays.asList("C", "J")));
        graph.put("J", new ArrayList<String>(Arrays.asList("I")));
 
        System.out.println(bfsFunc(graph, "A"));
    }
 
    private static ArrayList<String> bfsFunc(HashMap<String, ArrayList<String>> graph, String startNode) {
 
        //방문한 노드 List
        ArrayList<String> visited = new ArrayList<String>();
 
        //방문 필요한 노드 List
        ArrayList<String> needVisit = new ArrayList<String>();
 
        needVisit.add(startNode);
 
        while(needVisit.size() > 0){
            //BFS는 큐의 구조를 갖는다.
            String node = needVisit.remove(0);
 
            //방문 리스트에 없는 노드면 추가.
            if(!visited.contains(node)){
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }
 
        return visited;
    }
}

• A - B - C - D - G - H - I - E - F - J