BFS(Breadth First Search)

• 그래프 탐색의 한 종류로 너비 우선 탐색이라고 함
• 루트 노드나 임의의 노드에서 인접한 노드를 모두 먼저 확인한 후 다음 depth를 탐색
• Queue를 사용하여 데이터를 탐색

BFS의 흐름

전제 조건
1. 1번 정점을 root 노드로 하여 1번부터 탐색을 시작한다.
2. 번호가 작은 정점부터 탐색한다.

탐색 전 그래프

1단계

• 1번 정점을 큐에 추가한다.

2단계

• 1번 정점을 큐에서 제거한다.
• 1번 정점에서 탐색할 수 있는 정점이 있는 지 확인한다.
• 전제조건 2번에 번호가 작은 정점 먼저 탐색하기로 되어있으니 2번과 3번 중 2번 정점을 큐에 추가한다.

3단계

• 너비 우선 탐색이므로 2번과 동일한 너비인 3번 정점도 큐에 추가한다.

4단계

• 큐에서 2번을 제거한다.
• 2번과 인접하면서 동일한 깊이의 정점을 모두 큐에 추가한다.
  • 전제조건 2번으로 4번, 5번 순서로 큐에 추가한다.

5단계

• 4단계와 동일한 방법으로 3을 큐에서 제거하고 6번, 7번 정점을 큐에 추가한다.

6단계

• 동일한 방법을 반복해 모든 정점을 탐색한다.

탐색 결과

• 탐색된 정점 순서 : 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15
• 스택에서 제거되는 순서 : 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15

BFS 구현 방법

1. 탐색을 시작할 정점을 큐에 추가한다.
2. 추가한 정점을 큐에서 꺼낸다.
3. 꺼낸 정점과 연결되어있고 방문하지않은 모든 정점을 큐에 추가한다.
4. 원하는 조건 혹은 목적지에 도착할 때까지 반복한다.

그래프를 구현하는 2가지 방법으로 BFS 구현하기

인접 행렬(Adjacency Matrix)

• 행렬을 이용해 정점들 사이의 관계를 표현
• 보통 2차원 배열로 표현한다.
• 노드^2 만큼의 공간을 차지하므로 정점의 수가 적거나 간선의 수가 많을 경우 사용
• 간선 방향의 존재 유무에 따라 표현하는 방법에 차이가 있음
• 가중치가 있다면 간선 존재 유무 칸에 가중치를 적어주면 된다.

BFS 중요 코드

• 2차원 배열 기반의 코드로 정점 연관 관계 저장

package com.company;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class bfs {
    // 필요하면 사용 (사용안할 때도 많음)
    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int vertex;          // 정점의 수
    static int edge;            // 간선의 수
    static int[][] map;         // 정점들의 연관 관계를 담는 배열
    static boolean[] visit;     // 정점 방문 상태를 담는 배열

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

        vertex = sc.nextInt();
        edge = sc.nextInt();
        map = new int[vertex + 1][vertex + 1];
        visit = new boolean[vertex + 1];

        for (int i = 1; i <= edge; i++) {
            int start = sc.nextInt();
            int next = sc.nextInt();

			// 인접 행렬에 정점 연관 관계 저장
            map[start][next] = 1;
            map[next][start] = 1;
        }
        bfs(1, vertex);
    }

    public static void bfs(int start, int end){
        // 주로 LinkedList를 사용함
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(start,end));
        visit[1] = true;

        while (!queue.isEmpty()) {
        	// 정점 하나를 꺼냄
            Node node = queue.poll();
            visit[node.x] = true;
            // 꺼낸 정점에 연결된 정점들 중 방문하지 않은 모든 정점을 queue 넣음
            for (int i = 1; i < map.length; i++) {
                if(!visit[i] && map[node.x][i] == 1) {
                    queue.add(new Node(i, end));
                    visit[i] = true;
                }
            }
        }
    }
}

인접 리스트

• 각 정점이 연결된 노드들의 정보를 저장
• 간선 방향의 존재 유무에 따라 출발지 도착지를 고려하여 리스트에 정보 저장
  • 주로 ArrayList나 LinkedList로 구현
  • 정점이 많을 경우, 간선이 적을 경우 사용하면 인접 행렬보다 공간적 이득을 봄

package com.company;

import java.util.*;

public class bfs {

    static boolean[] visit;                     // 정점 방문 상태를 담는 배열
    static ArrayList<Integer>[] arrayList;      // 정점들의 연관 관계를 담는 리스트


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

        int vertex = sc.nextInt();
        int line = sc.nextInt();
        int startVertex = sc.nextInt();
        arrayList = new ArrayList[vertex + 1];
        visit = new boolean[vertex + 1];

        for (int i = 0; i < arrayList.length; i++) {
            arrayList[i] = new ArrayList<>();
        }

        for (int i = 0; i <= line; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            // arrayList로 연결 관계 저장
            arrayList[x].add(y);
            arrayList[y].add(x);
        }

        for (int i = 1; i < vertex + 1; i++) {
            Collections.sort(arrayList[i]);
        }

        bfs(startVertex);
    }

    public static void bfs(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visit[x] = true;

        while (!queue.isEmpty()) {
            int y = queue.poll();
            System.out.print(y + " ");
            for (int c : arrayList[y]) {
                if(!visit[c]) {
                    visit[c] = true;
                    queue.add(c);
                }
            }
        }
    }
}

썸네일 출처

Pixabay로부터 입수된 mohamed Hassan님의 이미지 입니다.