깊이 우선 탐색 (DFS)

1. BFS와 DFS

대표적인 그래프 탐색 알고리즘

너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식

깊이 우선 탐색 (Depth First Search) : 정점과 자식들을 먼저 탐색하는 방식

 

출처 : https://fastcampus.co.kr/courses/210773/clips/

 

2. DFS 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class Main3 {
    public static Integer node;
    public static ArrayList<ArrayList<Integer>> adj =  new ArrayList<>();
    public static Boolean visited[] = new Boolean[node];

    public static void addEdge (Integer node1, Integer node2) {
        adj.get(node1).add(node2);
    }

    public static void dfs (Integer node) {
        if (visited[node]) return;

        visited[node] = true;
        System.out.println(node + " ");

        for (int i = 0; i < adj.get(node).size(); i++) {
            int adjNode = adj.get(node).get(i);
            dfs(adjNode);
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        node = sc.nextInt();

        for (int i = 0; i < node + 1; i++) {
            adj.add(new ArrayList<Integer>());
        }

        Integer node2 = sc.nextInt();

        addEdge(node, node2);
    }
}

 

3. 시간 복잡도

노드수 : V

간선수 : E

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