Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
Tags
- JPA
- Java
- Oracle
- spring
- 파이썬
- 데이터
- 자료구조
- 프로그래머스
- 스프링부트
- backjoon
- 스프링 부트 쇼핑몰 프로젝트 with JPA
- baekjoon
- CS
- Spring Security
- javascript
- springboot
- python
- 자바
- 백준
- postgresql
- 네트워크
- 자바스크립트
- DB
- 데이터베이스
- 시큐리티
- 스프링
- Flutter
- CS지식
- 플러터
- 리눅스
Archives
- Today
- Total
Jin's Dev Story
[자료구조] DFS & BFS 본문
깊이우선탐색 - DFS
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 → 정점의 자식들을 먼저 탐색하는 방식
- 스택
- 자기 자신을 호출하는 순환 알고리즘의 형태를 지님
- 인접리스트로 표현된 그래프 : O(N+E)
- 인접 행렬로 표현된 그래프 : O(N^2)
public class DFS {
public static void main(String[] args) {
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")));
System.out.println(dfsFunc(graph, "A"));
}
private static ArrayList<String> dfsFunc(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){
//BFS와 다르게 DFS는 스택 구조이다.
String node = needVisit.remove(needVisit.size() - 1);
if(!visited.contains(node)){
visited.add(node);
needVisit.addAll(graph.get(node));
}
}
return visited;
}
}
- A - C - I - J - H - G - B - D - F - E
너비우선탐색 - BFS
- 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
- 재귀적으로 동작 X
- 선입 선출
- 큐
public class BFS {
public static void main(String[] args) {
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")));
System.out.println(bfsFunc(graph, "A"));
}
private static ArrayList<String> bfsFunc(HashMap<String, ArrayList<String>> graph, String startNode) {
//방문한 노드 List
ArrayList<String> visited = new ArrayList<String>();
//방문 필요한 노드 List
ArrayList<String> needVisit = new ArrayList<String>();
needVisit.add(startNode);
while(needVisit.size() > 0){
//BFS는 큐의 구조를 갖는다.
String node = needVisit.remove(0);
//방문 리스트에 없는 노드면 추가.
if(!visited.contains(node)){
visited.add(node);
needVisit.addAll(graph.get(node));
}
}
return visited;
}
}
- A - B - C - D - G - H - I - E - F - J
'CS 지식 > [자료구조]' 카테고리의 다른 글
[자료구조] 와일드카드(Wildcards) (0) | 2023.10.20 |
---|---|
[자료구조] 제네릭(generic) (0) | 2023.10.20 |
[자료구조] 빅오 표기법(big-O notation) (1) | 2023.10.20 |
[자료구조] 자료구조 (1) | 2023.10.20 |
[자료구조] HashMap (0) | 2023.08.01 |