BFS 이해

DFS & BFS 이해하기 및 구현(C++) (tistory.com)

DFS & BFS 이해하기 및 구현(C++)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool visited[9];
vector<int> graph[9];

// BFS 함수 정의
void bfs(int start) {
    queue<int> q;
    q.push(start); // 첫 노드를 queue에 삽입
    visited[start] = true; // 첫 노드를 방문 처리

    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void) {
    // 노드 1에 연결된 노드 정보 저장 
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);

    bfs(1);
}

위 코드는 BFS에서 제일 많이 쓰이고 보이는 풀이방식이다.

1. 우선 graph를 그래프로 표현해보면

2	1	1	3	3	7	2	1
3	7	4	5	4		6	7
8		8				8

   1           2          3          4           5         6         7          8             (인덱스)

이렇게 될 것이다. 인덱스는 트리에서 해당 노드를 의미하고, 그 안의 값들은 각 인덱스와 연결된 노드들을 의미한다.

bfs는 서로 이렇게 연결된 트리를 나타내기 위해서 보통

vector<int> graph[9] 와 같이 생겨져 있다.(배열 크기는 인덱스+1 이유는 node를 0부터 사용 x, 1부터 사용하기 위해)

bfs 트리 형태를 나타내기 위한 첫 번째 요소이다.

 

2. 그리고 또 하나 추가적으로 필요한 것이 visited배열이다.

이는 그래프의 크기와 똑같이 이루어져 있으며, bool형태인 경우가 많다.

 

1,2는 bfs함수 밖에서 전역변수로 선언하여 그때그때 값을 바꿔서 함수 밖을 나왔을 때도 그 결과가 유지되어야 한다.

3. queue는 1,2와 다르게  bfs 내에서만 쓰이는 temp와 같은 역할을 한다.

이 queue는 트리에서 한 깊이마다 push되며, 참조가 끝나면 pop되는 형태이다.

bfs에서는 이것이 비어지면 bfs연산이 끝나고 모든 요소를 돌았다고 판단한다.

 

처음에는 queue에 첫 노드를 넣어주고 해당 노드의 visited도 true로 시작하여 while문을 실행한다.

while문을 돌 때마다 새로 참조할 노드가 정해지며, 참조되는 즉시 pop된다.

 

2

3

8

두번쨰 깊이에서 queue 안은 이런식.

이제 해당노드에 연결된 노드들의 크기만큼(graph[x].size())만큼 돌며, visited한 적이 있으면 넘어가고 visited하지 않았으면 queue에 새로 push해준 뒤 visited를 true로 바꿔준다.

 

---

보통의 bfs는 위와 같은 형식으로 이루어진다.