참고
Graph의 DFS/BFS
NOTE
DFS/BFS 방법으로 그래프의 모든 노드를 방문할 수 있다!
•
Tree에서 사용한 방법과 유사하게 구현할 수 있으나 차이점이 존재한다.
•
Graph에서는 “방문했던 정점을 저장하는 방법”이 추가되어야 무한 루프가 발생하지 않고 모두 방문이 가능하다.
Graph의 DFS 동작과 구현
NOTE
깊이 우선 탐색
public void dfs(int vertex){
Stack<Integer> stack = new Stack();
HashSet<Integer> visited = new HashSet<>();
stack.push(vertex);
while (!stack.isEmpty()) {
int current = stack.pop();
if(!visited.contains(current)) {
visited.add(current);
for(int v : vertices[current]){
if(!visited.contains(v)) stack.push(v);
}
}
}
}
Java
복사
스택, 재귀 어떤 방식을 사용해도 상관없다.
Graph의 BFS 동작과 구현
NOTE
너비 우선 탐색
public void bfs(int vertex) {
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
queue.add(vertex);
visited.add(vertex);
while (!queue.isEmpty()) {
int current = queue.poll();
for (int v : vertices[current]) {
if(!visited.contains(v)){
visited.add(v);
queue.add(v);
}
}
}
}
Java
복사
Queue를 이용한 구현
최단 경로(Shortest path)
NOTE
Grpah의 BFS탐색은 최단 경로를 찾는데 사용할 수 있다!
현재 깊이의 모든 노드를 방문한 후에 다음 깊이의 모든 노드를 탐색하기 떄문에, 최단 경로를 찾을 수 있다!
public int findShortestDistance(int src, int dest){
Queue<Integer> queue = new LinkedList<>();
Map<Integer, Integer> distances = new HashMap<>();
queue.add(src);
distances.put(src, 0);
while (!queue.isEmpty()) {
int current = queue.poll();
int distance = distances.get(current);
if(current == dest) return distance;
for (int v : vertices[current]) {
if(!distances.containsKey(v)){
queue.add(v);
distances.put(v, distance + 1);
}
}
}
return -1;
}
Java
복사
•
만약 간선에 가중치가 있는 경우에는 다익스트라(DIjkstra) 알고리즘을 사용해야 하는데, 이는 다른 글에 정리해서 올리겠다.