너비 우선 탐색 (Breadth First Search, BFS)

너비 우선 탐색 (Breath First Search, BFS)는?

- 탐색시 너비를 우선으로 탐색을 수행하는 탐색 알고리즘

- 맹목적인 탐색을 하고자 할 때 사용

- 최단 경로를 찾아줌 -> 최단 길이를 보장해야 할 때 사용

- 자신에게 연결된 모든 사람에게 연락을 취하는 방식

- 특징 :

• 1부터(시작점으로부터) 가까운 노드들부터 탐색이 이루어짐
• 그래프 탐색일 경우 방문 여부 검사 필수
• 재귀적 동작 X
• FIFO (선입선출)
• 큐를 이용해서 반복적 형태로 구현하는 것이 일반적

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int m = sc.nextInt();
    int startNum = sc.nextInt();
    
    boolean[] visited = new boolean[n+ 1];
    LinkedList<Integer>[] adjList = new LinkedList[n + 1];
    
    for(int i = 0; i < (n+ 1); i++ {
    	adjList[i] = new LinkedList<Integer>();
    }
    
    for(int i = 0; i < m; i++) {
    	int v1 = sc.nextInt();
        int v2 = sc.nextInt();
        adjList[v1].add(v2);
        adjList[v2].add(v1);
    }
    
    for(int i = 1; i < (n+1); i++) {
    	Collections.sort(adjList[i]));
    }
    
    bfs_list(v, adjList, visited);
 }
 
 public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
 	Queue queue = new LinkedList<Integer>();
    
    visitied[v] = true;
    queue.add(v);
    
    while(queue.size() != 0) {
    	v = queue.poll();
        System.out.print(v + " ");
        
        Iterator<Integer> iter = adjList[i].listIterator();
        
        while(iter.hasNext()){
        	int w = iter.next();
            if(!visited[w]) {
            	visited[w] = true;
                queue.add(w);
            }
        }
    }
 }

• 큐 : 방문 차례의 기록을 목적으로 사용
  • 연락을 취할 정점의 순서를 기록하기 위한 것
  • 마지막 연락을 받은 사람 또한 연락을 취할 대상이 없는지 꼭 확인할 것
• 배열 : 방문 정보의 기록 목적

[LinkedList 이용해서 구현하면 좋음]

 

* 출처 : https://minhamina.tistory.com/36