죠노이 노트

[알고리즘] 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

티스토리툴바