DFS: 깊이 우선 탐색 = 깊은 부분 우선 탐색 → 스택 자료 구조/재귀 함수 이용

이런 식으로 전체 노드를 방문, 만약 인접한 노드가 없다면 다시 꺼내면 됨(pop) 따라서 탐색 순서: 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5
import java.util.*;
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>>graph = new ArrayList<ArrayList<Integer>>();
//dfs 함수 정의
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);
}
}
//생략
}
BFS: 너비 우선 탐색 = 가까운 노드부터 우선 탐색 → 큐 자료구조 이용

먼저 시작 노드를 큐에 삽입하고, 이를 꺼내서 인접한 노드를 삽입하는 것을 반복 이미 방문 처리한 것은 그냥 두면 됨 따라서 탐색 순서: 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6
import java.util.*;
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>>graph = new ArrayList<ArrayList<Integer>>();
//dfs 함수 정의
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
//현재 노드 방문 처리
visited[start] = true;
//큐가 빌 때까지 반복
while(!q.isEmpty()) {
//큐에서 하나의 원소를 뽑아 출력
int x = q.poll();
Ststem.out.print(x + " ");
//해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for (int i = 0; i < graph.get(x).size();i++) {
int y = graph.get(x).get(i);
if(!visited[y]) {
q.offer(y);
visited[y] = true;
}
}
}
//메인 함수 생략
}