깊이 우선 탐색(DFS) 유향 그래프 -JAVA 구현

• 유향 그래프와 무향 그래프의 차이점

그래프에서 유향 그래프와 무향 그래프의 차이는 변(간선)을 이루는 꼭짓점(노드)들이 서로서로 연결되어있는지, 아니면 편도로 연결되어 있는지이다. 유향 그래프의 경우에는 하나의 꼭짓점이 다른 꼭짓점으로 편도적인 연결을 이루고, 무향 그래프는 변을 이루는 꼭짓점들이 서로서로를 연결한다.  

 

• DFS 유향 그래프 구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static boolean[] seen; //방문 여부 배열
    static int[][] G; //유향 그래프 배열
    static int N,M;
    static void dfs(int[][] G, int v){
        seen[v] = true;
        System.out.print(v+ " ->");
        for(int next_v : G[v]){
            if(next_v == -1) continue; //두 꼭짓점이 관계성을 가지지 않을 때는 continue
            if(seen[next_v] ) continue;  //이미 방문한 적 있는 꼭짓점이라면 continue

            dfs(G, next_v); //재귀호출
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
        String input[]=bf.readLine().split(" ");
        N = Integer.parseInt(input[0]); //꼭짓점의 개수 N
        M = Integer.parseInt(input[1]); //변의 개수 M
        G = new int[N][N];
        seen= new boolean[N];
        for(int n=0; n<N; n++){
            Arrays.fill(G[n],-1); //두 꼭짓점 사이에 연결이 없는 경우는 -1
        }

        Arrays.fill(seen,false); //seen 배열의 초깃값은 false
        for(int i=0; i<M; i++){
            input = bf.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b= Integer.parseInt(input[1]);
            G[a][b] = b; // a->b 일 때 G[a][b] = b 값을 저장한다.
        }
        //input process


        for(int v=0; v<N; v++){ //한 꼭짓점에 대해 dfs가 완전히 끝나서 return되면 해당 for문으로 돌아온다.
            //예를 들어 v=0 일 때, 0와 연관된 꼭짓점에 대한 수행을 모두 마치면 return되어 이 for문으로 돌아온다.
            //그렇다면 v=1에 대해서 1와 연관된 꼭짓점에 대한 수행을 또 수행한다.
            if(seen[v]) continue; //방문한 적 있는 꼭짓점은 continue 
            // 만약 0과 1이 변을 이루고 있었다면  continue되어 v는 2가 되며, 2에 대한 dfs를 다시 수행하게 된다. 
            dfs(G,v);
        }
        //main process


    }
}

testCase

8 12 4 2 4 6 4 1 1 6 1 3 6 7 3 7 3 0 7 0 0 5 2 5 2 7