BFS 코드

bfs 함수에서는

(1) push()하자마자 check=true로 만들어주고

(2) 큐가 비어있지 않는 한 계속 반복할때마다

front()를 pop() 해주는 것이 꽤나 중요해보인다.

 

그러다보니 첫노드는 그야말로 큐에 들어가자마자(push) 빠져나오게(pop)게 된다.

 

main 함수에서는

차분하게 인접리스트를 구현해야한다.

 

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

using namespace std;

vector<int> numbers[7];
int check[7];

void bfs(int start)
{
    queue<int> que;
    que.push(start);
    check[start] = true;
    while (!que.empty())
    {
        int x =que.front();
        que.pop();
        cout << x << endl;
        for (int i = 0; i < numbers[x].size(); i++)
        {
            int z = numbers[x][i];
            if (!check[z])
            {
                que.push(z);
                check[z] = true;
            }
        }
    }
}

int main()
{
    numbers[1].push_back(2);
    numbers[2].push_back(1);

    numbers[1].push_back(3);
    numbers[3].push_back(1);

    numbers[2].push_back(3);
    numbers[3].push_back(2);

    numbers[2].push_back(4);
    numbers[4].push_back(2);

    numbers[2].push_back(5);
    numbers[5].push_back(2);

    numbers[3].push_back(6);
    numbers[6].push_back(3);

    numbers[3].push_back(7);
    numbers[7].push_back(3);
    bfs(1);
    return 0;

}

출력

1234567