DFS

DFS

정점의 자식들을 먼저 탐색하는 방식
한 노드의 자식을 타고 끝까지 순회한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다.

예제

needVisit 스택과, visited 큐를 사용한다.

visited
needVisit	A

---

visited	A
needVisit	B	C

---

visited	A	C
needVisit	B	A	G	H	I

---

visited	A	C	I
needVisit	B	A	G	H	C	J

---

visited	A	C	I	J
needVisit	B	A	G	H	C	I

---

visited	A	C	I	J
needVisit	B	A	G	H

---

visited	A	C	I	J	H
needVisit	B	A	G	C

---

visited	A	C	I	J	H	G
needVisit	B	A	C

---

visited	A	C	I	J	H	G	B
needVisit	D

---

visited	A	C	I	J	H	G	B	D
needVisit	E	F

---

visited	A	C	I	J	H	G	B	D	F
needVisit	E	D

---

visited	A	C	I	J	H	G	B	D	F
needVisit	D

---

예제 코드

    public Queue<String> solution(HashMap<String, List<String>> graph, String startNode) {
        Stack<String> needVisit = new Stack<>();
        Queue<String> visited = new LinkedList<>();

        needVisit.add(startNode);

        while (!needVisit.isEmpty()) {
            final String node = needVisit.pop();

            if (!visited.contains(node)) {
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }
        return visited;
    }

    public static void main(String[] args) {
        final DfsExam T = new DfsExam();

        HashMap<String, List<String>> graph = new HashMap<>();
        graph.put("A", new ArrayList<>(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList<>(Arrays.asList("A", "D")));
        graph.put("C", new ArrayList<>(Arrays.asList("G", "H", "I")));
        graph.put("D", new ArrayList<>(Arrays.asList("E", "F")));
        graph.put("E", new ArrayList<>(Arrays.asList("D")));
        graph.put("F", new ArrayList<>(Arrays.asList("D")));
        graph.put("G", new ArrayList<>(Arrays.asList("C")));
        graph.put("H", new ArrayList<>(Arrays.asList("C")));
        graph.put("I", new ArrayList<>(Arrays.asList("C", "J")));
        graph.put("J", new ArrayList<>(Arrays.asList("I")));

        System.out.println(T.solution(graph, "A").toString());
    }

• 시간복잡도 :
  • 노드 수 : V
  • 간선 수 : E
    = O(V+E)