BFS(넓이우선탐색, Breadth First Search)

넓이 우선 탐색은 처음 시작 정점을 방문한 뒤, 정점에서 인접한 모든 정점들을 우선 방문한다.

방문하지 않은 정점이 없어질 때까지 다른 모든 정점들에 대해서도 같은 방식으로 넓이 우선탐색을 수행한다.

넓이우선탐색은 선입선출 원칙으로 탐색을 해야 하기 때문에 Queue를 사용하게 된다.

인접행렬

public boolean[] visited;
public int[][] graph;

public void bfs(int node) {
    Queue<Integer> queue = new <Integer>LinkedList();

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

    while (!queue.isEmpty()) {
        int visitNode = q.poll();

        for (int i = 0; i < graph[visitNode].length; i++) {
            if (graph[visitNode][i] == 1 && visited[i] == false) {
                queue.add(i);
                visited[i] = true;
            }
        }
    }
}

// 그래프가 disconnected 이거나 방향그래프여서 모든 노드가 방문 불가능할때, 모든 노드 방문 시키기
public void bfsAll() {
    for (int i = 0; i < graph.length; i++) {
        if (visited[i] == false) {
            bfs(i);
        }
    }
}

인접리스트

public boolean[] visited;
public ArrayList<ArrayList<Integer>> graph;

public void bfs(int node) {
    Queue<Integer> queue = new <Integer>LinkedList();

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

    while (!queue.isEmpty()) {
        int visitNode = q.poll();

        for (int connectedNode : graph.get(visitNode)) {
            if (visited[connectedNode] == false) {
                queue.add(connectedNode);
                visited[connectedNode] = true;
            }
        }

        // 위 for문은 아래와 같은 의미이다.
        ArrayList<Integer> connectableNodeList = graph.get(visitNode);
        for (int i = 0; i < connectableNodeList.size(); i++) {
            int connectedNode = connectableNodeList.get(i);
            if (visited[connectedNode] == false) {
                queue.add(connectedNode);
                visited[connectedNode] = true;
            }
        }
    }
}

// 그래프가 disconnected 이거나 방향그래프여서 모든 노드가 방문 불가능할때, 모든 노드 방문 시키기
public void bfsAll() {
    for (int i = 0; i < graph.size(); i++) {
        if (visited[i] == false) {
            bfs(i);
        }
    }
}