BFS

 

 

 

이진 탐색과 순차 탐색처럼 특정 자료구조 내부를 탐색하는 알고리즘이 있듯, BFS는 그래프 자료구조를 탐색하는 알고리즘이다.

 

풀 네임은 Breadth-First Search으로, 너비 우선 탐색을 의미한다.

 

 

 

 

BFS는 위와 같이 탐색을 진행한다.

 

그래프에서 레벨에 해당하는 부분을 탐색하고, 하나의 레벨에 대해 탐색을 마치면 다음 레벨에 대해 탐색을 시작하며 마지막 모든 원소를 확인할 때 까지 탐색을 진행한다.

 

 

BFS를 구현하기 위해 먼저 Java에서 그래프를 구현하는 방법에 대해 알아보자.

 

자바에서는 HashMap과 ArrayList자료구조를 이용해 그래프를 구현한다.

 

HashMap의 Key부분에는 그래프의 노드에 해당하는 정보가 들어가고, Values부분에는 해당 노드에 인접한 노드에 대한 정보가 들어간다. 

 

Values에는 여러 가지 값이 들어갈 수 있으므로 ArrayList로 묶어서 처리해줘야 한다.

 

 

위에 있는 그래프를 자바 코드로 구현하면 다음과 같다.

 

HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();

graph.put("A", new ArrayList<String>(Arrays.asList("B", "C")));
graph.put("B", new ArrayList<String>(Arrays.asList("A", "D")));
graph.put("C", new ArrayList<String>(Arrays.asList("A", "G", "H", "I")));
graph.put("D", new ArrayList<String>(Arrays.asList("B", "E", "F")));
graph.put("E", new ArrayList<String>(Arrays.asList("D")));
graph.put("F", new ArrayList<String>(Arrays.asList("D")));
graph.put("G", new ArrayList<String>(Arrays.asList("C")));
graph.put("H", new ArrayList<String>(Arrays.asList("C")));
graph.put("I", new ArrayList<String>(Arrays.asList("C", "J")));
graph.put("J", new ArrayList<String>(Arrays.asList("I")));

 

 

이제 BFS를 구현해보자.

 

 

1. 큐 자료구조 두 개를 선언한다. (visited, needvisited)

 

2. 그래프에서 탐색을 시작할 노드를 지정해, 선언한 자료구조에 넣어준다. (needvisited)

 

3. needvisited의 사이즈가 1 이상이라면 poll을 수행 후 그 값을 visited에 넣어주고, 해당 노드가 가진 values들을 needvisit에 넣어준다.

 

4. 3을 반복한다. 반복 중 이미 방문한 노드에 대해서는 방문하지 않고 진행한다.

 

5. 모든 노드를 방문했으면 탐색을 중단한다.

 

 

 

 

import java.util.*;
import java.io.*;

public class Main {
    public Queue<String> bfsFunc(HashMap<String, Queue<String>> grpah, String startNode) {

        Queue<String> visited = new LinkedList<String>();
        Queue<String> needVisit = new LinkedList<String>();
        
        needVisit.add(startNode); // 시작 부분에 추가해줘야 한다.
        int count = 0;
        
        while (needVisit.size() > 0) { // 탐색해야 하는 부분이 남아있다면 탐색 수행
            count += 1;
            String node = needVisit.poll();
            
            if (!visited.contains(node)) {
                visited.add(node);
                needVisit.addAll(graph.get(node)); // 해당 노드의 ArrayList를 모두 추가
            }
        }
        return visited;
    }
}

 

 

visited에는 탐색한 순서대로 노드가 기록되어있다.

 

시간복잡도 : O(V+E) Vertex는 노드 수, Edge는 간선의 수