너비 우선 탐색 (BFS)

1. BFS와 DFS

대표적인 그래프 탐색 알고리즘

너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식

깊이 우선 탐색 (Depth First Search) : 정점과 자식들을 먼저 탐색하는 방식

 

출처 : https://fastcampus.co.kr/courses/210773/clips/

 

2. BFS 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class Main {
    public static Integer node;
    public static ArrayList<ArrayList<Integer>> adj =  new ArrayList<>();

    public static void addEdge (Integer node1, Integer node2) {
        adj.get(node1).add(node2);
    }

    public static void bfs (Integer newNode) {
        Boolean visited[] = new Boolean[node];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[newNode] = true;
        queue.add(newNode);

        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.println(now + " ");
            for (int i = 0; i < adj.get(now).size(); i++) {
                int adjNode = adj.get(now).get(i);
                if (!visited[adjNode]) {
                    visited[adjNode] = true;
                    queue.add(adjNode);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        node = sc.nextInt();

        for (int i = 0; i < node + 1; i++) {
            adj.add(new ArrayList<Integer>());
        }

        Integer node2 = sc.nextInt();

        addEdge(node, node2);
    }
}

 

3. 시간 복잡도

노드수 : V

간선수 : E

시간 복잡도 : O(V + E)