깊이 우선 탐색


그래프 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

넓이 우선 탐색이란?


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



동작 원리


먼저 거리가 1인 정점을 모든 찾은 후 2인 정점을 찾는 식으로 거리를 늘려가며 탐색

탐색을 하면서 시작점으로부터의 거리와 바로 직전 정점을 계산



직전정점 그래프(넓이 우선 탐색 트리)


시작점으로부터 각 정점에 들려야 하는 정점으로 만든 하위 그래프로 트리 형태

모든 정점이 연결되어 있고 nE(간선의 수) = nV(vertex의 수) - 1



예시)


주어진 그래프



1을 시작점으로한 넓이 우선 탐색 트리






코드 구현


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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class BfsExample {
    
    /*
     * 인접리스트로 구현된 그래프의 넓이우선 탐색
     */
    
    static int nV; //총 vertex 개수
    static int nE; //총 edge 개수
    static ArrayList<ArrayList<Integer>> adList = new <ArrayList<Integer>> ArrayList();
    //그래프 구현을 위한 인접리스트
 
    static int[] visit; //방문여부와 완료여부를 표시
    // 0 - 방문 안함,   1 - 방문했지만 아직 탐색 안됨 , 2 - 탐색완료
    static int[][] vertexInfo; //vertex의 위치 정보를 담는 2차원 배열
                               //i번쨰 vertex의 정보 - vertexInfo[i][0] = distance
                               //                   vertexInfo[i][1] = preVertex(상위 vertex)
    
    public static void bfs(int i) {
        visit = new int[nV];
        vertexInfo = new int[nV][2];
        Queue<Integer> q = new LinkedList();
 
        q.offer(i); //탐색 시작 위치의 vertex를 큐에 넣는다.
        visit[i] = 1;
        vertexInfo[0][i] = 0;
        while(!q.isEmpty()) { //Queue의 모든 작업이 없을때 까지
            int temp = q.poll(); //Queue에서 작업(탐색을 위한 데이터)을 가져온다.
            int tempDistance = vertexInfo[temp][0]; 
            for(int j:adList.get(temp)) { //인접리스트에서 temp번째 vertex가 가지고 있는 간선 수만큼 반복
                if(visit[j]==0) { //vertex에 한번도 방문 안했을떄
                    visit[j] = 1; //방문 체크를 한다.
                    vertexInfo[j][0] = tempDistance + 1;
                    vertexInfo[j][1] = temp; //상위 vertex 정보를 넣는다.
                    System.out.println(temp + "에서 " + j + "로 이동");
                    q.offer(j); //새로 찾은 vertex를 탐색하기 위해 Queue에 삽입
                }
            }
            visit[temp] = 2; //탐색 완료된 vertex 플래그
        }    
    }
 
    public static void main(String[] args) {
        
        //인접리스트를 이용한 그래프 구현
        Scanner scan = new Scanner(System.in);
 
        nV = scan.nextInt();
        nE = scan.nextInt();
 
 
        for(int i=0;i<nV;i++) adList.add(new<Integer> ArrayList());
        //adList에 담을 리스트(각 vertex마다 인접한 vertext를 표현한 리스트)
 
        for(int i=0;i<nE;i++) {
            int vertex1, vertex2;
            vertex1 = scan.nextInt();
            vertex2 = scan.nextInt();
 
            adList.get(vertex1).add(vertex2);
            adList.get(vertex2).add(vertex1);
        }
        
        //넓이우선 탐색시작
        bfs(1);
        
        int i = 0;
        for(int[] vertex:vertexInfo) {
            System.out.print(i++ + "-");
            System.out.print("distance" + vertex[0] + ", ");
            System.out.println("preVertex" + vertex[1]);
        }
    }
}
cs


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

[Map] HashMap  (0) 2017.03.10
[Set]HashSet의 특징  (1) 2017.03.09
[그래프] 인접리스트와 인접행렬을 이용한 구현  (0) 2017.02.26
ArrayList와 LinkedList  (0) 2017.01.02
Array 배열 for Java  (0) 2016.12.23

+ Recent posts

티스토리툴바