너비 우선 탐색 (BFS)
BFS 와 DFS ?
대표적인 그래프 탐색 알고리즘
너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
깊이 우선 탐색 (Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식
예제
BFS : A - B - C - D - G - H - I - E - F- J
- 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회
DFS : A - B - D - E - F - C - G - H - I - J
- 한 노드의 자식을 끝까지 순회 한 후, 같은 레벨에 있는 노드들의 자식을 순회
Java 로 그래프를 표현하는 방법
HashMap 과 ArrayList 를 활용해서 그래프를 표현 할 수 있음
BFS 알고리즘 구현
자료구조 큐를 활용함
큐의 구현은 ArrayList 클래스를 활용
import java.util.*;
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
String node = list.remove(0);
System.out.println(list); // [B]
System.out.println(node); // A
System.out.println(list.contains("A")); // false
import java.util.*;
public class BFSSearch {
public ArrayList<String> bfsFunc(HashMap<String, ArrayList<String>> graph, String startNode) {
ArrayList<String> visited = new ArrayList<>();
ArrayList<String> needVisited = new ArrayList<>();
needVisited.add(startNode);
while(needVisited.size() > 0) {
// 첫 노드
String node = needVisited.remove(0);
if(!visited.contains(node)) {
visited.add(node);
needVisited.addAll(graph.get(node));
}
}
// visited 에는 방문한 순서가 기록되어있음
return visited;
}
}
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")));
BFSSearch search = new BFSSearch();
search.bfsFunc(graph, "A"); // [A, B, C, D, G, H, I, E, F, J]
시간 복잡도
노드 수 : V
간선 수 : E
시간복잡도 (O(V + E))
feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스
'코테 > 알고리즘' 카테고리의 다른 글
최단 경로 알고리즘 - 1 (1) | 2023.10.18 |
---|---|
탐욕 알고리즘 (0) | 2023.09.12 |
그래프 이해 (0) | 2023.09.04 |
동적 계획법과 분할 정복 (0) | 2023.08.30 |
재귀 호출 (0) | 2023.08.30 |