[알고리즘][DFS] DFS 기본 개념

[알고리즘][DFS] DFS 개념

• 그래프 탐색의 종류

1. DFS (DepthFirstSearch)     ; 스택
2. BFS (BreadthFirstSearch)   ; 큐

• 그래프 탐색의 목적 

- 모든 정점을 1번씩 방문

• 깊이우선탐색 (DFS)

• 스택을 이용해 갈 수 있는 만큼 최대한 많이 간다.
• 갈 수 없을 경우, 스택에서 빼고 이전으로 돌아간다.

[코드]

• 재귀를 이용한 DFS 탐색 코드

- 인접 행렬을 이용한 코드 구현

    int n = scan.nextInt(); //접점의 수
    int m = scan.nextInt(); //간선의 수
    int[][] array = new int[n][m];
    boolean[] check = new boolean[n];
    
    public void DFS1(int x) {
        check[x] = true;
        
        for(int i=0;i<=n;i++) {
            if(array[x][i]==1 && check[i]==false) {
                check[i] = true;
                DFS1(i);
            }
        }
    }

- 인접 리스트를 이용한 코드 구현

    ArrayList<ArrayList<Integer>> a = new ArrayList<>(); //스택
    boolean[] check = new boolean[n];
    
    public void DFS2(int x) { 
        check[x] = true;    
    
        for(int i=0;i<a.get(x).size();i++) {
            int y = a.get(x).get(i);
            if(check[y]==false) {
                DFS2(y);
            }
        }
    }