너비우선탐색
- 정점들과 같은 레벨에 있는 노드(형제 노드)를 먼저 탐색하는 방식!
- BFS : A -> B -> C -> D -> G -> H -> I -> E -> F -> J
- 한 단계씩 내려가면서. 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다.
이 그래프를 Hashmap 과 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 알고리즘 구현
- 자료구조 '큐'를 활용한다!
=> 큐 : 먼저 넣은 데이터가 제일 먼저 나온다! (들어간 순서대로 데이터가 빠져나옴)
needVisit Queue 와 Visited Queue 두 개의 큐를 생성하여 구현할 수 있다!
예를들어 보면,,
위 그래프에서 A부터 방문하게 될 것이다.
그럼 방문해야 하는 (needVisit) 곳에 A를 넣어주고
A를 방문하고 나면(visited에 추가) 방문해야 하는 노드는 B와 C이므로
이것을 각 각 needVisit에 채워주는 형식이다.
이것이 1회이고, 이후에도 같은 방식으로 돌면된다.
(needVisit의 사이즈가 0보다 큰지 비교 => 방문할 노드가 남았다는 뜻)
그 다음엔, needVisit 에서 B가 우선이므로 (Queue이기에 먼저 들어간 노드가 먼저 나옴)
B를 방문하고 (visited에 추가) B에 연결된 노드를 차례로 needVisit에 추가한다.(A와D)
이렇게 2회가 끝나게 된다.
그 다음 똑같이 needVisit의 사이즈가 0보다 크기 때문에 마찬가지로
C를 방문하고, needVisit에 C와 연결된 노드들을 추가하여주는데,
needVisit을 보면 A가 들어가있는 것을 볼 수 있다.
needVisit은 이미 방문한 노드이기 때문에(visited) 아무것도 하지 않고 다음 반복을 진행한다.
또한 방문하고나면 needVisit 에서 해당 노드를 삭제하여준다(!!)
...
class BFSSearch {
public ArrayList<String> bfsFunc(HashMap<String, ArrayList<String>> graph, String startNode) {
ArrayList<String> visited = new ArrayList<String>();
ArrayList<String> needVisit = new ArrayList<String>();
needVisit.add(startNode);
while(needVisit.size() > 0) {
String node = needVisit.remove(0);
if(!visited.contains(node)) {
visited.add(node);
needVisit.addAll(graph.get(node));
}
}
return visited;
}
}- 시간복잡도
- 일반적인 BFS 시간 복잡도- 노드 수:V (A,B,C,D,G,H,I,E,F,J => 10개)
- 간선 수:E (연결된 선 => 9개)
- 위 코드에서 while(needVisit)은 V + E 만큼 수행함
- 따라서 시간 복잡도는 O(V+E)
