[그래프] 깊이 우선 탐색(DFS)

깊이 우선 탐색

그래프 G와 시작점 S가 주어졌을 때 S에서 도달 가능한 모든 간선을 찾는 과정

동작원리

탐색 시작 위치의 vertex의 인접한 간선을 통해 다른 vertex로 이동한 후 인접한 간선이 없을 때까지

반복하여 내려간 후 다시 위로 올라가는 과정을 반복해서 탐색하는 것

아래로 깊이 내려가며 탐색하기에 깊이 우선 탐색이라고 불림

코드)

public class DfsExample {
    
    /*
     * 인접행렬로 구현된 그래프의 깊이 우선 탐색
     */
    
    static int nV; //총 vertex 수
    static int nE; //총 edge 수
    static int[][] adMatrix; //인접행렬
    static boolean[] visit; //방문여부 체크
    
 
    //재귀호출을 이용한 dfs구현
    
    public static void dfs(int i) {
        visit[i] = true;
        for(int j=0;j<nV;j++) {
            if(adMatrix[j][i]==1 && !visit[j]) {
                System.out.println(i + "에서 " + j + "로 이동");
                dfs(j);
            }
        }    
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        nV = scan.nextInt();
        nE = scan.nextInt();
        
        adMatrix = new int[nV][nV];
        visit = new boolean[nV];
        
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
            adMatrix[vertex2][vertex1] = 1;
        }
        
    
        for(int i=0;i<nV;i++) {
            System.out.print(i + "-" );
            for(int j=0;j<nV;j++) {
                System.out.print(adMatrix[j][i]+ " ");
            }
            System.out.println();
        }
 
        
        dfs(0);
    }
}