BFS(Breadth First Search)란?
-
BFS는 DFS와 함께 대표적인 그래프 탐색 알고리즘으로, node들과 같은 레벨에 위치한 node들 먼저 탐색을 해나가는 방법이다.
-
즉, 시작 node로부터 가까운 node들을 먼저 방문하고 멀리 떨어져있는 node들을 나중에 순회하는 알고리즘이다.
-
사용하는 경우 - 두 node사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
- ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
- DFS - 모든 친구 관계들을 다 살펴보며 탐색한다.
- BFS - Ash와 가까운 관계부터 탐색해간다.
BFS의 특징
- 재귀적으로 동작하지 않는다.
- visited list와 같이 방문을 한 node의 list를 만들어 체크를 하지 않으면 무한루프에 빠질 위험이 있다.
- 방문한 node들을 차례대로 저장 후 꺼낼 수 있도록 Queue를 사용한다.
- Prim, Dijkstra 알고리즘과 유사하다.
BFS 예제
Java 코드로 구현
package algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
// BFS는 visited, needVisited를 모두 queue로 구성
public class BFS {
public static void main(String[] args) {
HashMap<String, String[]> grapgh = new HashMap<>();
String[][] nodeInfo = {{"B","C","D"},
{"A", "E", "F"},
{"A"},
{"A"},
{"B","G","H"},
{"B"},
{"E"},
{"E"}};
// nodeInfo에는 A~H순서대로 각 Node당 연결된 node들을 저장해둔다.
// HashMap에는 put을 통해 바로 array를 넣을 수 없기에 이렇게 지정해야한다.
grapgh.put("A", nodeInfo[0]);
grapgh.put("B", nodeInfo[1]);
grapgh.put("C", nodeInfo[2]);
grapgh.put("D", nodeInfo[3]);
grapgh.put("E", nodeInfo[4]);
grapgh.put("F", nodeInfo[5]);
grapgh.put("G", nodeInfo[6]);
grapgh.put("H", nodeInfo[7]);
System.out.println(bfs(grapgh, "A"));
}
public static List<String> bfs(HashMap<String, String[]> grapgh, String search){
List<String> visited = new ArrayList<>();
List<String> needVisit = new ArrayList<>();
String node;
needVisit.add(search);
while (!needVisit.isEmpty()) {
node = needVisit.remove(0);
// node가 visited에 없으면 visited에 추가 및 node의 연결된 node를 need_visited에 추가!
if (!visited.contains(node)) {
visited.add(node);
needVisit.addAll(Arrays.asList(grapgh.get(node)));
// addAll은 list데이터를 넣어야하기에 array로 되어있는
// grapgh.get(node)의 값을 List로 변경 후 넣어준다.
}
}
return visited;
}
}🔗 Reference
블로그 이전했습니다. -> https://seongwon.dev/