DFS와 BFS 개념 및 구현

DFS(Depth-First Search) : 그래프를 탐색할 때, 현재 위치에 인접한 노드를 우선적으로 선택하여 깊이가 증가하는 방향으로 탐색하는 알고리즘

 

 

구현 : 재귀를 이용 (그래프 표현 방법 : 인접 행렬)

static int[][] graph;
    
static boolean[] visited;


static void dfs(int node){
    visited[node] = true;
    System.out.print(node + " ");
    for (int i = 0; i <= n; i++) {
        if(graph[node][i] == 1 && !visited[i]){
            dfs(i);
        }
    }
}

 

 

BFS(Breadth First Search) : 시작 정점부터 옆으로 좌우로 탐색하는 너비 우선 탐색 방법

 

구현 : 큐를 이용 (그래프 표현 방법 : 인접 행렬)

static int[][] graph;
static boolean[] visited;


static Queue<Integer> q;
static void bfs(int node){
    q = new LinkedList<>();
    q.add(node);
    visited[node] = true;

    while (!q.isEmpty()){
        int now = q.poll();
        System.out.print(now + " ");
        for (int i = 0; i <= n ; i++) {
            if(graph[now][i] == 1 && !visited[i]){
                q.offer(i);
                visited[i] = true;
            }
        }
    }

}