728x90
깊이 우선 탐색(DFS)
DFS(Depth-First Search) 는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색
하는 알고리즘이다.
DFS 는 Stack
자료구조를 사용하며 Stack 을 이용하기 때문에 재귀 함수를 이용하면 쉽게 DFS 구현을 할 수 있다.
재귀와 Stack 에 대해서 잘 모르겠으면 해당 링크를 통해서 배우고 오자.
동작 과정
Step1
Step1. 시작 노드를 스택에 넣고 방문 처리한다.
Step2
Step2. 방문하지 않은 인접 노드 중에서 번호가 가장 낮은 곳을 방문하고 해당 노드를 스택에 넣어 방문 처리 한다.
Step3
Step3. 위 과정을 반복한다.
구현
public class Main {
public static boolean[] visited = new boolean[9];
public static List<List<Integer>> graph = new ArrayList<>();
// Depth-First Search
public static void dfs(int x) {
// 현재 노드를 방문 처리
visited[x] = true;
System.out.print(x + " ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited[y]) {
dfs(y);
}
}
}
public static void main(String[] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(5);
graph.get(2).add(8);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(4);
graph.get(3).add(6);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(7);
// dfs 시작
dfs(1);
}
}
References
728x90
'Algorithms > 기본 지식' 카테고리의 다른 글
조합(Combination) (0) | 2022.01.03 |
---|---|
부분 집합 구하기(DFS) (0) | 2022.01.03 |
위상 정렬 (0) | 2021.12.14 |
신장 트리와 크루스칼 알고리즘 (0) | 2021.12.13 |
서로소 집합 (0) | 2021.12.12 |