C++ BFS

---

<BFS>

BFS는Depth First Search의 줄임말로 깊이 우선 탐색이라는 뜻이다.

-시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

-큐를 사용하여 구현할 수 있다.

---

<BFS과정>

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다

 

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리한다

 

3. 2번의 과정을 반복한다.

---

<BFS장단>

장점	출발노드에서 목표노드까지의 최단 길이 경로를 보장한다
단점	경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요하고 무한 그래프이면 무한루프에 빠지게 된다.

---

<BFS구현>

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

bool visited[1001];
vector<int> graph[1001];
void Bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < graph[x].size(); i++)
        {
            int y = graph[x][i];
            if (!visited[y])
            {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}