[알고리즘] BFS란?

이번 글에서는 그래프를 탐색하는 방법 중 하나인 BFS에 대해서 다뤄보겠습니다.

 

---

BFS란?

BFS는 Breath-First Search의 줄임말로, 하나의 정점에서 시작하여 해당 정점과 이웃한 모든 정점을 방문한 뒤, 방문한 정점들의 이웃 정점을 방문하는 방식을 의미합니다.

 

BFS의 탐색 순서를 아래의 그림을 통해 쉽게 확인하실 수 있습니다.

BFS

 

BFS의 구현

BFS를 자바로 구현해보겠습니다.

import java.util.*;

public class Edge{ // 각 노드를 정의
	int adjvertex;
    public Edge(int v){
    	adjvertex = v;
    }
}

public class BFS{
	int N;
    List<Edge>[] graph;
    private boolean[] visited;
    
    public BFS(List<Edge>[] adjList){
    	N = adjList.length;
        graph = adjList;
        visited = new boolean[N];
        
        for(int i=0; i<N; i++){
        	if(!visited[i]) bfs();
        }
	}
    
    private void bfs(int i){
    	Queue<Integer> q = new LinkedList<>();
        visited[i] = true;
        q.add(i);
        
        while(!q.isEmpty()){
        	int j = q.poll();
            System.out.print(i+" ");
            for(Edge e : graph[j]){
            	if(!visited[e.adjvertex]){
                	visited[e.adjvertex] = true;
                    q.add(e.adjvertex);
                }
            }
        }
    }   
}

 

DFS에서는 재귀를 이용하여 구현하였지만, DFS는 큐를 이용하여 구현합니다. 큐를 이용해서 인접한 노드를 큐에 넣고 하나씩 pop하면서 사용하는 방식을 이용합니다.

 

어려운 난이도의 코드는 아니니 자세한 설명은 생략합니다.

 

예시를 통한 코드의 수행 과정 그림을 첨부하였으니 확인하면 되겠습니다.

 

프로그램 수행 결과로 0 -> 2 -> 1 -> 3 -> 8 -> 9 -> 4 -> 5 -> 6 -> 7이 되겠습니다.

 

---

DFS와 비슷한 맥락으로 BFS를 거친 간선만을 살려 나타내면 너비 우선 신장 트리가 만들어집니다.

 

---

BFS의 수행 시간

BFS 또한 DFS와 동일하게 최악의 경우 모든 정점과 모든 간선을 거쳐야하므로 O(n+m)이 되고, 여기서 n은 간선 m은 정점의 개수를 의미합니다.

---

간단하게 BFS에 대해서 알아봤습니다. DFS와 유사한 개념이라 빠르게 지나가봤는데, 혹시 이해가 안가신다면 다른 글 또는 댓글 남겨주시면 감사하겠습니다.