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

너비 우선 탐색이란?

- 루트 노드(or 다른 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다.

- 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방법이다.

 

BFS의 사용

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 주로 사용한다.

 

BFS의 특징

1. 재귀적으로 동작하지 않는다.
2. 어떤 노드를 방문했었는지 반드시 검사해야 한다.
3. 큐(Queue)를 사용한다.
   • 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용하는 것이다.
4. 'Prim', 'Dijkstra' 알고리즘과 유사하다.
5. DFS보다 좀 더 복잡하다.

 

BFS의 장점

• 노드의 수가 적고 깊이가 얕은 경우 빠르게 탐색이 가능하다.
• 단순 검색 속도로는 DFS보다 빠르다.
• 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러개인 경우에도 최단 경로를 보장한다.

 

BFS의 단점

• 큐에 다음에 탐색할 정점들을 저장해야 하므로 이에 따라 많은 저장공간을 필요로 한다.
• 노드의 수가 많을수록 탐색할 노드 또한 많아지기 때문에 시간이 오래 걸린다.

 

BFS 과정

BFS의 과정을 이해하기 위해 그래프 자료구조를 아주 살짝 짚고 넘어가 보자.

---

그래프의 구성

그래프는 노드(Node)와 간선(Edge)으로 표현되며, 노드를 정점(Vertex)으로 표현하기도 한다.

쉽게 생각했을 때, 노드(또는 정점)를 도시로 표현한다면 간선은 도시와 도시를 잇는 도로라고 생각할 수 있다.

위와 같이 노드가 간선으로 연결되어 있다면 두 노드는 '인접(Adjacent)'해있다고 하며,

그래프 탐색이란 하나의 노드에서 시작하여 다른 노드들을 방문하는 것을 의미한다.

---

본론으로 돌아와, BFS는 그래프에서 가까운 노드부터 우선적으로 탐색하기 위해 '큐'를 활용한다.

좀 더 설명하자면, 인접한 노드를 반복적으로 큐에 삽입하고 먼저 삽입된 노드부터 차례로 큐에서 꺼내는 방식이다.

전체적인 동작 과정은 아래와 같다.

1. 탐색 시작 노드 정보를 큐에 삽입하고 '방문 처리'한다.
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.(큐가 빌 때까지)

*방문처리를 하는 이유?

 어떤 노드를 방문했었는지 여부를 검사하지 않으면, 무한 루프에 빠질 수 있는 위험이 있기 때문이다.

 

BFS 흐름 예시

주황색: 방문한 노드

파란색: 방문 전 노드

가장 먼저 시작 정점(A)을 방문 처리하고, 큐에 시작 정점을 넣는다.

큐의 가장 앞에 있는 노드(현재 A노드)를 빼고, 해당 노드의 인접 노드를 조사한다.

 

- B노드는 방문하지 않았으므로, 방문처리를 하고 큐에 넣는다.

- C노드는 방문하지 않았으므로, 방문처리를 하고 큐에 넣는다.

- E노드는 방문하지 않았으므로, 방문처리를 하고 큐에 넣는다.

큐의 가장 앞에 있는 노드(현재 B노드)를 빼고, 해당 노드의 인접 노드를 조사한다.

 

- A노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

- C노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

큐의 가장 앞에 있는 노드(현재 C노드)를 빼고, 해당 노드의 인접 노드를 조사한다.

 

- B노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

- A노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

- D노드는 방문하지 않았으므로, 방문처리를 하고 큐에 넣는다.

큐의 가장 앞에 있는 노드(현재 E노드)를 빼고, 해당 노드의 인접 노드를 조사한다.

 

- A노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

- D노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

- C노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

큐의 가장 앞에 있는 노드(현재 D노드)를 빼고, 해당 노드의 인접 노드를 조사한다.

 

- C노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

- E노드는 이미 방문하였으므로, 방문하지 않고 큐에도 넣지 않는다.

 

큐가 비었기 때문에 BFS를 종료한다.

 

BFS 알고리즘의 의사 코드(Pseudo-Code)

위의 BFS 구현 과정을 간단하게 의사 코드로 표현하자면 다음과 같다.

BFS(G,v) // 그래프 G, 탐색 시작 정점 v
	큐 생성
    	시작 정점 v를 큐에 삽입
    	정점 v에 대한 방문 체크
    	while(큐가 비어 있지 않은 경우){
    		t <- 큐의 첫번째 원소 반환
       	 for(t와 연결된 모든 간선에 대해){
        		u <- t의 인접 정점
          	  u가 방문되지 않은 곳이면,
          	  u를 큐에 넣고, 방문한 것으로 표시
          	  }
   	  }
end BFS()

 

BFS 알고리즘의 코드 구현-java

BFS는 그래프를 인접 리스트, 인접 행렬 두 가지로 표현할 수 있다.

두 가지를 전부 알아보자.

 

인접 리스트로 구현한 BFS

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); //정점의 개수
int m = sc.nextInt(); //간선의 개수
int v = sc.nextInt(); //탐색을 시작할 정점의 번호

LinkedList<Integer>[] adjList = new LinkedList[n+1];

for(int i=0; i<=n; 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=0; i<=n; i++){
	Collections.sort(adjList[i]); //방문 순서를 위해 오름차순으로 정렬한다.
}

처음 BFS 함수를 호출하면 int v에 탐색을 시작할 정점의 번호가 들어있고, 이 시작 정점부터 탐색을 시작한다.

큐를 생성하고 시작 정점 v의 값을 큐에 넣는다.

그리고 위에서 설명했던 구현 방법대로 BFS를 수행한다.

public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited){
	Queue<Integer> queue = new LinkedList<Integer>();
    	visited[v] = true;
    	queue.add(v);
    
    while(queue.size() != 0){
    	v = queue.poll();
        System.out.print(v+" ");
        
        Iterator<Integer> iter = adjList[v].listIterator();
        while(iter.hasNext()){
        	int w = iter.next();
           	 	if(!visited[w]) {
          			visited[w] = true;
                		queue.add(w);
            	}
        }
    }
}

입력과 출력은 다음과 같다.

• 입력

5 5 3
5 4
5 2
1 2
3 4
3 1

• 출력

3 1 4 2 5

 

인접 행렬로 구현한 BFS

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); //정점의 개수
int m = sc.nextInt(); //간선의 개수
int v = sc.nextInt(); //탐색을 시작할 정점의 번호

boolean visited[] = new boolean[n+1]; //방문 여부를 검사할 배열

int[][] adjArray = new int[n+1][n+1];

/*
두 정점 사이에 여러 개의 간선이 있을 수 있으며,
입력으로 주어지는 간선은 양방향이다.
*/
for(int i=0; i<m; i++){
	int v1 = sc.nextInt();
    	int v2 = sc.nextInt();
    
    	adjArray[v1][v2] = 1;
    	adjArray[v2][v1] = 1;
}

값을 입력받고 그래프를 구성하는 방법에 차이가 있을 뿐, BFS알고리즘에는 큰 차이가 없다.

public static void bfs_array(int v, int[][] adjArray, boolean[] visited){
	Queue<Integer> queue = new LinkedList<>();
    	int n = adjArray.length -1;
    
	queue.offer(v);
    	visited[v] = true;
    
    	while(!q.isEmpty()){
    		v = q.poll();
       		System.out.print(v+" ");
        
       		for(int i=1; i<=n; i++){
        		if(adjArray[v][i] == 1 && !visited[i]){
            		q.offer(i);
                	visited[i] = true;
           		}
        	}
    	}
}

입력과 출력은 다음과 같다.

• 입력

4 5 1 3
1 2
1 3
1 4
2 4
3 4

• 출력

1 2 3 4

 

BFS 시간 복잡도

정점의 수가 n이고, 간선의 수가 e인 그래프의 경우 시간 복잡도는 다음과 같다.

• 인접 리스트 : O(n+e)
• 인접 행렬 : O(n^2)

희소 그래프는 인접 리스트를 사용하는 것이 인접 행렬을 사용하는 것보다 유리하다.(사용 메모리의 차이)

*희소 그래프: 그래프 내에 적은 수의 간선을 갖는 그래프

 

 

참고 블로그

https://minhamina.tistory.com/36

[Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현

https://heytech.tistory.com/56

[알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog