죠노이 노트

[알고리즘] Graph - DFS(깊이 우선 탐색) [ 펌 - manducku]

개발/알고리즘2016. 10. 22. 00:18
이번 포스팅에서는 그래프의 대표적인 두 개의 탐색 중, DFS(깊이 우선 탐색)에 대해 공부해 보도록 하겠습니다.

DFS 정의
     간단하게 이야기하면 갈수있을 때까지 간다입니다.
     즉, 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라 갑니다.
     이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아가면서 탐색이 이루어 집니다.

DFS 진행 과정 


위 그래프를 1부터 깊이 우선 탐색 방법으로 탐색해보도록 하겠습니다.
깊이 우선 탐색의 경우, 내가 지나간 곳을 계속해서 추적해야 하기 때문에 스택이 필요 합니다.



1. 1번을 방문하고, 1번 방문에 대한 정보를 stack에 입력합니다.


2. 1번과 연결된 두 개의 정점 중 하나인 5를 선택하여 이동하고, stack에 5를 입력 합니다. 


3. 5번과 연결된 정점 3개 중, 방문하지 않은 정점 중 하나인 3을 선택하여 이동하고, stack에 3을 입력합니다.


4. 3번과 연결된 정점 중, 방문 하지 않은 정점 중 하나인 2를 선택하여 이동하고, stack에 2를 입력합니다.


5. 2번과 연결된 정점 중, 방문하지 않은 정점 중 하나인 2를 선택하여 이동하고, stack에 4를 입력합니다.


6. 4번과 연결된 정점을 찾아보니, 방문하지 않은 정점이 하나도 없습니다. 이 때 stack에서 4를 빼내고 2로 돌아갑니다. 


7. 기존에 했던 방식대로 , 2번에 연결된 정점 중, 방문하지 않은 정점 중 하나인 6을 방문합니다. 
그래프의 모든 정점을 탐색하였으므로, 그래프 탐색을 종료 합니다.

위와 같이 깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아가야 한다는 점입니다.
이 것을 구현하기 위에선 지금까지 거쳐온 정점들을 모두 저장해 둬야 하는데, 재귀 호출을 이용하면 이와 같은 일을 간단히 할 수 있습니다.
예시에서는 Stack을 예를 들었으나, 배열을 추가로 2개 만들어야하는 등 고려할 사항이 많기 때문에.. 비 추천합니다.

아래의 소스는 양반향 그래프를 인접행렬과 인접리스트로 구현한 소스입니다.

<인접행렬을 통해 구현한 DFS>
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
 
package Graph_07;
import java.util.*;
 
public class DfsTest {
    
    static int nE;
    static int nV;
    static int[][] ad;   
    static boolean[] visit; 
    
    public static void dfs(int i){
        visit[i] = true;   // 함수 호출 시, visit 했음을 표시
        System.out.print(i+ " ");
        
        for(int j = 1; j < nV+1; j++){
            if(ad[i][j] == 1 && visit[j] == false){  // j를 방문하지 않았으면 j를 방문한다.
                dfs(j);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        nV = scan.nextInt();
        nE = scan.nextInt();
        ad = new int[nV+1][nV+1]; // 변수 초기화
        visit = new boolean[nV+1]; // 변수 초기화
        
        for(int i = 0; i < nE; i++){
            int t1 = scan.nextInt();
            int t2 = scan.nextInt();
            
            ad[t1][t2] = ad[t2][t1] = 1;
        }
        
        dfs(1); // 1번부터 탐색 시작
        
    }
 
}
 
cs


<인접리스트을 통해 구현한 DFS>
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
package Graph_07;
import java.util.*;
 
public class DfsTest02 {
 
    static int Nv;
    static int Ne;
    static boolean[] visit;
    static ArrayList<ArrayList<Integer>> ad;
    
    public static void dfs(int i){
        visit[i] = true;
        System.out.print(i);
        
        for(int j : ad.get(i)){  // 배열 null check
            if(visit[j] == false){
                dfs(j);
            }
        }
    }
    
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        Nv = scan.nextInt();
        Ne = scan.nextInt();
        ad = new ArrayList(Nv+1); // 인접 리스트 초기화
        visit = new boolean[Nv+1]; // visit 배열 초기화
        
        for(int i = 0; i < Nv+1; i++){ // 인접 리스트 속의 리스트 초기화
            ad.add(new ArrayList());
        }
        
        for(int i = 0; i < Ne; i++){
            int t1 = scan.nextInt();
            int t2 = scan.nextInt();
            
            ad.get(t1).add(t2);
            ad.get(t2).add(t1);
        }
        
        dfs(1);    
    }
 
}
 
 
 
 
cs


'개발 > 알고리즘' 카테고리의 다른 글

[알고리즘] Graph - BFS (너비 우선 탐색) [펌 - manducku]  (0) 2016.10.22

[알고리즘] Graph - BFS (너비 우선 탐색) [펌 - manducku]

개발/알고리즘2016. 10. 22. 00:16
이번 포스팅에서는 그래프의 대표적인 두 개의 탐색 중, BFS(너비 우선 탐색)에 대해 공부해 보도록 하겠습니다.


BFS 정의

BFS는 현재 위치에 인접한 모든 위치의 노드를 방문하고, 그 이웃 노드들의 또 다른 이웃 노드들을 방문하는 것은 그 다음에 진행하는 것을 의미합니다. BFS를 가장 효과적으로 구현하는 방법은 큐를 이용해서 순환적 형태로 구현하는 것이 가장 깔끔합니다.


BFS 진행 과정 


위 그래프를 1부터 너비 우선 탐색 방법으로 탐색해보도록 하겠습니다.




최초에 방문할 노드를 큐에 삽입합니다. 



방문할 최초 노드의 값을 큐에서 꺼내고, 큐와 인접해 있는 노드들을 큐에 삽입 합니다.



방문할 노드의 값 5를 큐에서 꺼내고, 큐와 인접해 있는 노드들을 큐에 삽입합니다.
여기서 6은 기존에 큐에 값이 있으므로 해당 데이터는 중복해서 넣지 않도록 조심해야 합니다.
hash로 구현을 하든, visit 값을 미리 체크하던… 두 가지 방법으로 중복을 방지하도록 합시다



위와 같이, 방문할 노드 6을 큐에서 꺼내고, 큐와 인접한 노드들을 큐에 삽입합니다.
아래는 위 방법의 중복이므로 상세한 설명은 생략하도록 하겠습니다. 







최종적으로 큐가 비어있으면, 함수를 탈출합니다.


<인접 행렬, hashmap을 사용한 BFS 구현 소스>
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
package Graph_07;
import java.util.*;
 
public class BfsTest01 {
    
    static int Ne;
    static int Nv;
    static int[][] ad;
    static boolean[] visit;
    
    public static void bfs(int i){
        Queue<Integer> q = new <Integer> LinkedList();
        HashMap <Integer, Boolean> hash = new HashMap<Integer, Boolean>();  //hash Map을 이용하여 queue 입력여부 확인
        
        q.offer(i);
        
        while(!q.isEmpty()){
            int temp = q.poll();
            visit[temp] = true;
            System.out.print(temp);
            
            for(int j =1; j <= Ne; j++){
                if(ad[temp][j] == 1 && visit[j] == false){
                    if(!hash.containsKey(j)){
                        q.offer(j);
                        hash.put(j, true);
                    }
                }
            }
        }
    }
    
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Ne = scan.nextInt();
        Nv = scan.nextInt();
        
        ad = new int[Nv+1][Nv+1];
        visit = new boolean[Nv+1];
        
        for(int i = 0; i < Nv; i++){
            int t1, t2;
            t1 = scan.nextInt();
            t2 = scan.nextInt();
            
            ad[t1][t2] = ad[t2][t1] = 1;
        }
        
        bfs(1);
        
        
    }
 
}
 
 
 
cs

<인접 행렬, visit을 사용한 BFS 구현 소스>
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
package Graph_07;
import java.util.*;
 
 
public class BfsTest02 {
    
    static int[][] ad;
    static boolean[] visit;
    static int Ne, Nv;
    
    public static void bfs(int i){
        Queue <Integer> q = new <Integer> LinkedList();
        
        q.offer(i);
        visit[i] = true;
        
        while(!q.isEmpty()){
            int temp = q.poll();
            System.out.print(temp);
            
            for(int j = 1; j <= Nv; j++){
                if(ad[temp][j] == 1 && visit[j] == false){
                    q.offer(j);
                    visit[j] = true;                   // 큐에 넣을 노드들을 잠재적으로 방문한다는 가정하에 입력
                    }
                }
            
            }    
    }
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        Nv = scan.nextInt();
        Ne = scan.nextInt();
        ad = new int[Nv+1][Nv+1];
        visit = new boolean[Nv+1];
        
        for(int i = 0; i < Ne; i++){
            int t1, t2;
            t1 = scan.nextInt();
            t2 = scan.nextInt();
            
            ad[t1][t2] = ad[t2][t1] = 1;
        }
        
        bfs(1);
        
    }
    
}
 
 
 
 
cs


<인접 리스트, hashMap을 사용한 BFS 구현 소스>
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
package Graph_07;
import java.util.*;
 
public class Bfs03 {
    
    static ArrayList<ArrayList<Integer>> ad;
    static boolean[] visit;
    static int Ne, Nv;
    
    public static void bfs(int i){
        Queue <Integer>q = new <Integer> LinkedList();
        HashMap<Integer, Boolean> hash = new HashMap<Integer, Boolean>();
        
        q.offer(i);
        
        while(!q.isEmpty()){
            int temp = q.poll();
            visit[temp] = true;
            System.out.print(temp);
            
            for(int j : ad.get(temp)){
                if(visit[j] == false && !hash.containsKey(j)){
                    q.offer(j);
                    hash.put(j, true);
                }
            }
            
        }
        
        
    }
    
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Nv = scan.nextInt();
        Ne = scan.nextInt();
        ad = new <ArrayList<Integer>> ArrayList(Nv+1);
        visit = new boolean[Nv+1];
        
        for(int i = 0; i <= Nv+1; i++){
            ad.add(new ArrayList());
        }
        
        for(int i = 0; i < Ne; i++){
            int t1, t2;
            t1 = scan.nextInt();
            t2 = scan.nextInt();
            
            ad.get(t1).add(t2);
            ad.get(t2).add(t1);    
        }
        
        bfs(1);        
    }
 
}
 
 
 
 
cs



- 출처 http://manducku.tistory.com/24

'개발 > 알고리즘' 카테고리의 다른 글

[알고리즘] Graph - DFS(깊이 우선 탐색) [ 펌 - manducku]  (0) 2016.10.22

티스토리툴바