그래프 탐색 BFS, DFS

 

BFS

    public static void BFS(List<List<Integer>>graph, int start){
        int size=graph.size();
        Queue<Integer>que=new LinkedList<>();
        que.add(start);
        boolean[] visited=new boolean[size];
        visited[start]=true;
        while(!que.isEmpty()){
            int vertex=que.poll();
            System.out.println(vertex+" ");
            for(var nextV: graph.get(vertex)){
                if(!visited[nextV]){
                    que.add(nextV);
                    visited[nextV]=true;
                }
            }
        }
    }

아래는 List<List<Integer>> 를 List<Integer>[]로 바꾸어 표현한 것

//    public static void BFS(List<Integer>[]graph, int start){
//        int size=graph.length;
//        Queue<Integer>que=new LinkedList<>();
//        que.add(start);
//        boolean[] visited=new boolean[size];
//        visited[start]=true;
//        while(!que.isEmpty()){
//            int vertex=que.poll();
//            System.out.println(vertex+" ");
//            for(var nextV: graph[vertex]){
//                if(!visited[nextV]){
//                    que.add(nextV);
//                    visited[nextV]=true;
//                }
//            }
//        }
//    }

DFS (재귀버전)

public static void dfs(List<List<Integer>>graph, int start, boolean[]visited){
        if(!visited[start]){
            visited[start]=true;
            System.out.println(start+" visited");
            for(var nextV:graph.get(start))
                dfs(graph, nextV, visited);
        }
    }
    
public static void dfs(int[][]graph, int start, boolean[]visited){
    if(!visited[start]){
        visited[start]=true;
        System.out.println(start+" visited");
        for(var nextV:graph[start])
            dfs(graph, nextV, visited);
    }
}

DFS (스택사용)

    public static void dfs(List<List<Integer>> graph, int start) {
        int size = graph.size();
        boolean[] visited = new boolean[size];
        Deque<Integer> stack = new LinkedList<>();
        stack.add(start);
        visited[start] = true;
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            System.out.println(vertex + " visited");
            for (var nextV : graph.get(vertex)) {
                if (!visited[nextV]) {
                    visited[nextV] = true;
                    stack.push(nextV);
                }
            }
        }
    }
    public static void dfs(int[][] graph, int start) {
        int size = graph.length;
        boolean[] visited = new boolean[size];
        Deque<Integer> stack = new LinkedList<>();
        stack.push(start);
        visited[start] = true;
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            System.out.println(vertex + " visited");
            for (var nextV : graph[vertex]) {
                if (!visited[nextV]) {
                    visited[nextV] = true;
                    stack.push(nextV);
                }
            }
        }
    }