BFS, DFS 알고리즘

너비 우선 탐색 (BFS)

인접한 노드부터 탐색하는 방법으로 가까운 노드를 먼저 방문하고 멀리 떨어진 노드를 나중에 방문하는 방식입니다
큐를 이용하여 구현이 가능합니다

간단한 bfs 구현 코드

import java.util.*;

public class BFS{
    static Map<Integer, List<Integer>> graph;
    static HashMap<Integer, Boolean> visited;
    public static void main(String[] args) {
		    init();
        bfs(graph, 0);
    }
    // 그래프 및 방문기록 초기화
    public static void init(){
        graph = new HashMap<>();
        visited = new HashMap<>();
        graph.put(0, Arrays.asList(1, 3, 6));
        graph.put(1, Arrays.asList(0, 3));
        graph.put(2, Arrays.asList(3));
        graph.put(3, Arrays.asList(0, 1, 2, 7));
        graph.put(4, Arrays.asList(5));
        graph.put(5, Arrays.asList(4, 6, 7));
        graph.put(6, Arrays.asList(0, 5));
        graph.put(7, Arrays.asList(3, 5));
    }
    
    public static void bfs(Map<Integer, List<Integer>> graph, int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited.put(start, true);

        while(!queue.isEmpty()){
            int cur = queue.poll();
            // cur와 연결된 모든 노드 순회
            for(int next : graph.get(cur)){
            	// cur와 연결된 모든 노드들 중 방문하지 않은 노드들 큐에 저장
                if(!visited.containsKey(next)){
                    queue.offer(next);
                    visited.put(next, true);
                }
            }
        }
    }
}

---

깊이 우선 탐색 (DFS)

한 경로를 따라 최대한 깊이 탐색한 후 다음 경로를 탐색하는 방법입니다
스택 또는 재귀함수를 이용하여 구현이 가능합니다

간단한 dfs 구현 코드

import java.util.*;

public class DFS{
    static Map<Integer, List<Integer>> graph;
    static HashMap<Integer, Boolean> visited;
    public static void main(String[] args) {
        init();
        dfs(0);
    }
    public static void init(){
        graph = new HashMap<>();
        visited = new HashMap<>();
        graph.put(0, Arrays.asList(1, 3, 6));
        graph.put(1, Arrays.asList(0, 3));
        graph.put(2, Arrays.asList(3));
        graph.put(3, Arrays.asList(0, 1, 2, 7));
        graph.put(4, Arrays.asList(5));
        graph.put(5, Arrays.asList(4, 6, 7));
        graph.put(6, Arrays.asList(0, 5));
        graph.put(7, Arrays.asList(3, 5));
    }
    
    public static void dfs(int cur){
        visited.put(cur, true);
        // 현재 노드의 다음 노드를 방문 (재귀)
        for(int next : graph.get(cur)){
            if(!visited.containsKey(next)){
                dfs(next);
            }
        }
    }
}