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

    Untitled

    이런 식으로 전체 노드를 방문, 만약 인접한 노드가 없다면 다시 꺼내면 됨(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);
    			}
    		}
    		
    		//생략
    }
    
  2. BFS: 너비 우선 탐색 = 가까운 노드부터 우선 탐색 → 큐 자료구조 이용

    Untitled

    먼저 시작 노드를 큐에 삽입하고, 이를 꺼내서 인접한 노드를 삽입하는 것을 반복 이미 방문 처리한 것은 그냥 두면 됨 따라서 탐색 순서: 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;
    				}
    			}
    		}
    		//메인 함수 생략
    }