깊이 우선 탐색


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


동작원리


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

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


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



코드)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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);
    }
}
cs


'자료구조' 카테고리의 다른 글

[Map] HashTable과 HashMap의 차이와 Properties  (0) 2017.03.10
[Map] HashMap  (0) 2017.03.10
[Set]HashSet의 특징  (1) 2017.03.09
[그래프]넓이 우선 탐색(BFS)  (0) 2017.03.07
[그래프] 인접리스트와 인접행렬을 이용한 구현  (0) 2017.02.26

+ Recent posts

티스토리툴바