[알고리즘] DFS & BFS

DFS

> 원리

Stack 을 이용해서 갈 수 있는 만큼 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아감
Stack과 재귀호출을 이용해서 구현

> 인접 행렬로 구현

private void dfs(int start){
        check[start] = true;

        for(int i=1;i<N+1;i++){
            if(arr[start][i]==1 && !check[i])
                dfs(i);
        }
    }

시간 복잡도 : O(N^2)

> 인접 리스트로 구현

인접리스트와 원리는 같지만 모든 배열을 순회하는 것이 아닌 정점에 연결된 노드만 순회하므로 수행시간 일정하지 않음
시간 복잡도 : O(N+E)

BFS

> 원리

Queue를 이용하여 지금 위치에서 갈 수 있는 모든 위치를 큐에 넣음
Queue에 넣을 시점에 방문했다고 체크
Queue와 While을 이용하여 구현

> 인접 행렬로 구현

private void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        check[start] = true;

        while(!q.isEmpty()){
            int v = q.poll();
            
            for(int i=1;i<N+1;i++){
                if(arr[v][i]==1 && !check[i]){
                    q.offer(i);
                    check[i] = true;
                }
            }
        }
    }

시간 복잡도 : O(N^2)