forked from onlybooks/java-algorithm-interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGraphTraversalsExample.java
More file actions
90 lines (82 loc) · 3.29 KB
/
GraphTraversalsExample.java
File metadata and controls
90 lines (82 loc) · 3.29 KB
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package ch12;
import java.util.*;
public class GraphTraversalsExample {
static Map<Integer, List<Integer>> graph = new HashMap<>();
public static List<Integer> recursiveDFS(int v, List<Integer> discovered) {
// 현재 노드 저장(전위 순회)
discovered.add(v);
// 주변 노드 반복
for (Integer w : graph.get(v)) {
// 아직 처리되지 않은 노드라면 깊이 기반 탐색 진행
if (!discovered.contains(w)) {
discovered = recursiveDFS(w, discovered);
}
}
// 모든 깊이를 탐색하면 리턴
return discovered;
}
public static List<Integer> iterativeDFS(int v) {
// 결과 노드를 저장할 리스트 선언
List<Integer> discovered = new ArrayList<>();
// 스택 선언은 효율적인 ArrayDeque 자료형 사용
Deque<Integer> stack = new ArrayDeque<>();
// 현재 노드를 스택에 삽입
stack.push(v);
// 스택이 모두 비워질 때까지 반복
while (!stack.isEmpty()) {
// 스택에서 추출
v = stack.pop();
// 이미 방문한 노드가 아니라면 방문 노드에 추가하고 주변 노드를 모두 스택에 삽입
if (!discovered.contains(v)) {
discovered.add(v);
// 현재 노드에서 연결된 모든 주변 노드를 스택에 삽입
for (int w : graph.get(v)) {
stack.push(w);
}
}
}
// 더 이상 탐색할 노드가 없으면 리턴
return discovered;
}
public static List<Integer> iterativeBFS(int start_v) {
// 결과 노드를 저장할 리스트 선언
List<Integer> discovered = new ArrayList<>();
// 시작 노드 삽입
discovered.add(start_v);
// 큐는 인터페이스이며 자료형 선언은 LinkedList 사용
Queue<Integer> queue = new LinkedList<>();
// 시작 노드 삽입
queue.add(start_v);
// 큐가 모두 비워질 때까지 반복
while (!queue.isEmpty()) {
// 큐에서 추출
int v = queue.poll();
// 현재 노드에서 연결된 모든 주변 노드를 큐에 삽입
for (int w : graph.get(v)) {
// 이미 방문한 노드가 아니라면 방문 노드에 추가하고 주변 노드를 모두 큐에 삽입
if (!discovered.contains(w)) {
discovered.add(w);
queue.add(w);
}
}
}
// 더 이상 탐색할 노드가 없으면 리턴
return discovered;
}
public static void main(String[] args) {
graph.put(1, Arrays.asList(2, 3, 4));
graph.put(2, Arrays.asList(5));
graph.put(3, Arrays.asList(5));
graph.put(4, Arrays.asList());
graph.put(5, Arrays.asList(6, 7));
graph.put(6, Arrays.asList());
graph.put(7, Arrays.asList(3));
List<Integer> r = new ArrayList<>();
// 재귀 구조 DFS
System.out.println(recursiveDFS(1, r));
// 반복 구조 DFS
System.out.println(iterativeDFS(1));
// 반복 구조 BFS
System.out.println(iterativeBFS(1));
}
}