깊이 우선 탐색 (DFS)

깊이 우선 탐색 (DFS)

 

BFS 코드 참고

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")));

 

DFS 알고리즘 구현

스택과 큐를 활용함

간단히 ArrayList 클래스 활용

import java.util.*;

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
String node = list.remove(list.size() - 1);

System.out.println(list);    // [A]
System.out.println(node);    // B

 

public class DFSSearch {
    public 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) {
            String node = needVisit.remove(needVisit.size() - 1); // BFS와 이 부분만 다름 (큐 -> 스택)
            if (!visited.contains(node)) {
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }
        return visited;
    }
}

DFSSearch dObject = new DFSSearch();
dObject.dfsFunc(graph, "A");    // [A, C, I, J, H, G, B, D, F, E]

 

시간 복잡도

노드 수 : V

간선 수 : E

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

 

 

 

 

 

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스