BFS (너비 우선 탐색) 를 간단하게 알아보자.

BFS(Breath First Search)를 간단하게 설명하면?

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘!

 

시작 정점부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

큐를 이용하여 구현을 합니다.

 

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.  
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다. 
3. 위의 과정을 수행할 수 없을 때까지 반복합니다. 

 

BFS 구현 과정 

인접리스트

import java.util.*;
public class Main {

    public static boolean visited[];
    public static int v;
    public static int e;
    public static ArrayList<ArrayList<Integer>>  graph;
    
    public static void bfs(int start) {
    	Queue <Integer> q = new <Integer> LinkedList();
    	q.offer(start);  //첫 정점노드 삽입
    	visited[start] = true;
    	
    	while(!q.isEmpty()) {   //큐가 빌 때까지 
    		int a = q.poll();
			System.out.print(a+" ");
				
    		
    		for(int i=0; i < graph.get(a).size(); i++) {
    			int b = graph.get(a).get(i);
    			if(!visited[b]) {
    				q.offer(b);
    				visited[b]= true;
    			}
    		}
    	}
    }
    
    public static void main(String[] args) {
    	Scanner scan = new Scanner(System.in);
    	v = scan.nextInt();
    	e = scan.nextInt();
    	graph = new ArrayList<ArrayList<Integer>>(v+1);
    	visited = new boolean[v+1];
       
       for(int i=0; i<e; i++) {
    	   graph.add(new ArrayList());
    	   int t1 = scan.nextInt();
    	   int t2 = scan.nextInt();
    	   
    	   graph.get(t1).add(t2);
    	   graph.get(t2).add(t1);
       }
        bfs(1);
    }
}

 

인접 행렬

import java.util.*;
public class Main {

    public static boolean visited[];
    public static int v;
    public static int e;
    public static int[][] graph;   //인접 행렬 
    
    public static void bfs(int start) {
    	Queue <Integer> q = new <Integer> LinkedList();
    	q.offer(start);
    	visited[start] = true;
    	
    	while(!q.isEmpty()) {
    		int a = q.poll();
    		System.out.print(a+" ");
    		
    		for(int i=1; i<=v; i++) {
    			if(graph[a][i] ==1 && visited[i]==false) {  //노드값이 1이고, 방문하지 않았다면
    				q.offer(i);
    				visited[i]= true;
    			}
    		}
    	}
    }
    
    public static void main(String[] args) {
    	Scanner scan = new Scanner(System.in);
    	v = scan.nextInt();
    	e = scan.nextInt();
    	graph = new int[v+1][v+1];
    	visited = new boolean[v+1];
       
       for(int i=0; i<e; i++) {
    	   int t1 = scan.nextInt();
    	   int t2 = scan.nextInt();
    	   
    	   graph[t1][t2] = 1;
    	   graph[t2][t1] = 1;
       }
        bfs(1);
    }
}

 

시간 복잡도 

V: 정점

E: 간선

• 인접 리스트 : O(V + E)
• 인접 행렬 : O(V^2)