DFS and BFS

틀린 부분(틀린 이유)

BFS에서 현재 노드의 인접노드를 넣을 때, 현재 큐에서 뽑은 노드의 인접노드를 넣어주어야 하는데 처음 시작한 노드의 인접노드를 넣어버렸다! 그래서 첫 노드의 인접노드만 방문하고 탐색이 종료되었다!

1. DFS

public static void dfs(int x) {
        if (c[x]) {
            return;
        }
        c[x] = true;
        System.out.print(x + " ");
        for (int y : a[x]) {
            if (c[y] == false) {
            	//c[y] = true;
                dfs(y);
            }
        }
    }

2. BFS

public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        c[start] = true;
        while (!q.isEmpty()) {
            int x = q.remove();
            System.out.print(x + " ");
            for (int y : a[x]) {
                if (c[y] == false) {
                    c[y] = true;
                    q.add(y);
                }
            }
        }
    }

DFS와 BFS 구현의 차이

BFS : for(int y:a[x])문으로 인접리스트를 통해서 인접 노드를 방문하지 않았다면 true 처리하고, 큐에 넣는다.

DFS : for(int y:a[x])문 안에서 재귀호출만하고 true처리하지 않는다. 왜냐하면 이 for문 내에서 true로 처리해버리면 그 바로 밑에 재귀함수 호출에 들어가는 인자는 true가 되버려 DFS가 재귀호출되어도 바로 리턴되버리기 때문이다!

main 함수 구현 1. 인접리스트 : 정수형 ArrayList 배열 생성, 이용한다!

public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int start = sc.nextInt();
        a = (ArrayList<Integer>[]) new ArrayList[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = new ArrayList<Integer>();
        }
        for (int i=0; i<m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            a[u].add(v);
            a[v].add(u);
        }
        for (int i=1; i<=n; i++) {
            Collections.sort(a[i]);
        }
        c = new boolean[n+1];
        dfs(start);
        System.out.println();
        c = new boolean[n+1];
        bfs(start);
        System.out.println();
    }