BFS - Breadth First Search

안녕하세요 ❗️ 

오늘은 굉장히 유명한 알고리즘인 BFS/DFS 중 BFS를 집중적으로 살펴보려고 합니다.

 

살펴보기 전, BFS/DFS를 적용하는데 있어서 '그래프 Graph'라는 자료구조를 사용하는데요. 

지난 포스팅으로 '그래프 graph' 자료구조를 소개해드렸습니다. 

만약, 그래프 자료구조가 무엇인지 모르시는 분들은 한 번쯤 읽고 가시는 게 좋을 듯 싶습니다 〰️ 

 

이제부터 BFS가 무엇인지 알아가보도록 하겠습니다 ❗️ 

 

 

BFS ❓

그래프의 모든 노드를 순회하고자 할때, 인접한 노드들을 우선으로 방문하도록 구현합니다.

 

BFS와 비슷한 개념이 DFS는 Depth First Search이 있는데요.

DFS는 시작 노드를 기준으로 다음 노드를 선택할 때, 선택한 분기를 끝까지 순회하고 나서 다른 분기를 확인합니다. 

 

 

그럼, 어떨 때 BFS 방식인 '인접한 노드들을 우선적으로 사용'해야 능률이 늘어날 수 있을까요❓ 

 

SNS 친구로 예시를 한 번 들어보도록 하겠습니다. 

userA의 SNS 친구 관계가 Graph의 형식으로 표현되어 있을 때, userA와 userB의 사이를 알아보려면 BFS를 사용하여 더욱 빠르게 찾을 수 있을 것 입니다.

깊게(Deep) 탐색하기 전에 넓게(wide) 탐색하는 방법이죠.

 

추가로, DFS가 유리할 때도 알아볼까요❓ 

대표적으로 미로찾기가 있습니다. 미로를 찾을 때, 여러군데를 조금씩 방문하기보다는 한 길을 끝까지 갔다가 아니면 다른 길을 끝까지 가는 것이 더욱 효율적이겠죠? 

넓게(wide) 탐색하기 전에 깊게(Deep) 탐색하는 방법이죠.

 

 

자, 개념은 어느정도 익혔으니, 이젠 BFS의 과정을 살펴보도록 하겠습니다.

 

 

BFS 구현

코드로 구현해보기 전에, 어떤 방법으로 조회를 하는지 알아봐야 겠죠❓ 

 

 

 

 

위와 같은 그래프에서 BFS로 순회하는 과정을 같이 알아보도록 합시다 〰️

필요한 건, Adjacency list와 방문해야할 노드(vertex)가 들어있는 queue, 그리고 방문을 했는지 안했는지 확인하는 Boolean 배열이 하나 필요합니다.

 

 

제일 먼저, 시작 정점 방문으로 시작합니다.

 

 

일단, '2' 노드(vertex)를 방문했기 때문에 2가지의 변화가 생깁니다.

첫 번째로, visited[2]가 True로 변하고, Queue에 방문할 노드인 2를 push 했다가 poll (불러오고 Queue에서 삭제) 합니다.

두 번째로, Adjacency list의 2번 째 인덱스와 연결되어 있던 0과 3이 queue로 push 되게 됩니다.

 

그럼 아래와 같은 모습을 띄게 됩니다.

 

 

 

큐에 0과 3이 있으니, 이제 0과 3을 순서대로 방문합니다.

 

 

위와 같이 0을 조회했을 때, 0과 연결된 노드가 Queue에 추가되게 되는데, 2는 이미 visited[2] = true인 상태기 때문에 Queue에 추가되지 않습니다.

0을 조회하고 나서 0을 Queue에서 poll 시킵니다 〰️ 

 

0을 조회했다면, 다음으로는 어떤 것을 조회할까요❓ 

맞습니다 〰️ Queue에서 다음으로 빠져나올 3을 조회하겠죠❓ 

 

 

 

3을 조회하면 위와같이 됩니다.

 

이제 다음 차례인 1을 조회하러 갈 텐데요.

1은 0을 조회할 때 Queue에 추가되었습니다 〰️ 

 

 

 

1까지 조회한 상태입니다.

이 때, 1이 poll되고 나면 Queue는 비게 되는데요.

 

Queue가 빈다는 의미는 결국 다음 참조할 노드가 없다 == 모두 다 조회했다라는 의미가 됩니다.

따라서 BFS 탐색을 종료하는 조건이 될 수 있겠죠❓ 

 

자, 이렇게 BFS 과정을 함께 살펴보았습니다.

어느 정도 이해가 가셨나요 〰️ 

이제 부터는 코드를 통해 알아보도록 하겠습니다 ❗️ 

 

 

 

BFS 구현 - JAVA CODE

BFS를 구현한 코드를 같이 보도록 하겠습니다 〰️ 

 

import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v,int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);
        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s+" ");
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("starting from vertex 2");

        g.BFS(2);
    }
}

 

 

코드를 다음과 같은 순서로 함께 분석해봅시다 〰️ 

 

1. Graph

2. main

3. BFS

 

순서는 위와 같이 Graph라는 클래스의 속성과 메소드를 알아보고, 

main 메소드의 코드를 분석한 후,

BFS 메소드의 구현을 같이 살펴보도록 하겠습니다.

 

1. Graph

 

class Graph {
    private int V;                      // vertex의 수
    private LinkedList<Integer> adj[];  // 인접 리스트 - Adjacency Lists 

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v,int w) {
        adj[v].add(w);
    }
    // ...   
}

 

전체 코드 중 일부를 가져와 보았는데요.

 

일단 처음으로 봐야할 것은 Graph 생성자입니다.

v (=vertex의 수)를 넣어주면, 전역 변수인 V에 값을 넣어주고 vertex의 수 만큼 LinkedList를 생성하는 것이 보입니다. 

비어있는 adjacency lists를 생성하는 역할을 합니다.

 

두 번째로 볼 것은 addEdge 메소드인데요.

adj 라는 인접 리스트에 v번째 인덱스로 w(=vertex) 의 값을 추가해줍니다.

비어있는 adjacency lists를 연결되어 있는 Vertex를 추가함으로서 그래프를 생성하는 역할을 하고 있네요.

 

여기까지 어려움은 없을 것 같아요.

조금 어렵다면 Graph에 대한 이해가 부족해서 그럴 수도 있을테니, 그래프를 다시 알아가는 시간을 갖는 것도 좋을 것 같네요 〰️ 

 

 

2. main Method

이 번엔 main Method를 함께 살펴보도록 하겠습니다 〰️ 

 

import java.util.*;

class Graph {
    // ...
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("starting from vertex 2");

        g.BFS(2);
    }
}

 

굉장히 간단한 코드죠! 

Graph 생성자를 사용해서 g라는 객체를 생성했습니다. 

이 때, vertex의 개수를 4로 주어 빈 adjacency lists에 LinkedList 4개를 생성하였네요.

여기까지의 모습을 보면  [[], [], [], []]  의 모습을 띄고 있습니다.

 

addEdge로 adjacency lists를 완성시켜주었습니다.

모든 코드가 실행되면,   [[1, 2], [2], [0, 3], [3, 3]]   의 모습을 보여주겠죠❓ 

도식화하여 보면 아래와 같은 모습을 띄게 되겠죠 〰️ 

 

 

 

데이터 세팅이 끝나면 마지막으로 드디어 BFS Method를 실행시켜줍니다.

 

3. BFS

오늘의 주인공인 BFS 코드입니다.

하나씩 살펴보도록 하겠습니다 〰️

 

import java.util.*;

class Graph {
    // ... Graph generator
    
    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);
        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s+" ");
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
    
    // ... main
}

 

 

위에서 보았던 visited를 표시해줄 Boolean Array가 있는 것을 확인할 수 있네요.

또, 그 아래 다음 방문할 queue가 정의되어 있습니다. 

 

s 인자는 처음 노드를 표시해줍니다.

main을 보시면 2로 표시를 해주었죠. 

'2'노드가 시작점입니다. 그래서 visited[2] 를 true로 설정해 둔 것을 확인할 수 있습니다.

 

그 다음엔, queue가 비어있지 않다면 계속해서 탐색을 이어나가라는 의미의 while문이 있습니다.

queue에 저장되어 있는 노드를 하나씩 가져와서 연결되어 있는 노드를 하나씩 조회합니다.

만약 연결되어있는 게 있다면 가져와서 방문했는지 확인을 하고, 방문하지 않았다면 방문했다고 표시를 한 후 queue에 추가시킵니다.

 

이 과정을 계속하다보면, 모든 노드를 순회할 수 있게되죠.

 

위의 그림과 같이 보면 더욱 이해가 쉬울 것 같아요.

만약 보면서도 이해가 가지 않는다면, 직접 그리면서 이해하는 것도 좋을 것 같습니다. 

 

 

 

 

그럼, 이렇게 BFS 이 무엇인지, 어떻게 사용되는지 그리고  어떻게 코드로 구현하는지에 대해 살펴보았습니다.

코드는 Java를 사용하였는데, 만약 다른 언어(c++, python)를 사용하신 다면 이 링크를 통해 살펴보시는 것을 추천드립니다 〰️ 

 

그럼 BFS 포스팅을 마치도록 하겠습니다 〰️ 

오타나 오류 등이 있거나 소소한 이야기를 전달하고 싶다면 댓글로 남겨주세요 ❗️