BFS(Breadth first search)

Pseudo code

BFS(v)

    for(i=0;i<n;i++)

        visited[i] = false

    Queue = creaetQueue()

    Visited[v]  = true

    v 방문

    while(not isEmpty(Queue))

        While(visited[v의 인접정점 w] == false)

            Visited[w] = true

            W 방문

            Queue.push(w)

        v = q.pop()

//BFS(인접리스트) 내가 구현한 코드

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

/*7 7 1

1 2

1 3

2 4

2 5

3 6

3 7

6 7

*/

class graph{

public:

int vertex;//정점의 갯수

vector<vector<int>> edge;//간선 목록

vector<bool> visited;//방문 여부

queue<int> q;

graph(int n){

vertex = n;

edge.resize(n + 1);

visited.resize(n + 1, false);

}

void bfs(int v){

cout << v << " ";

visited[v] = true;

q.push(v);

while (!q.empty()){

v = q.front();

for (auto i : edge[v]){

if (!visited[i]){

cout << i << " ";

visited[i] = true;

q.push(i);

}

}

q.pop();

}

}

};

int main(){

int n, m, v, i, a, b;

graph *g;

cin >> n >> m >> v;

g = new graph(n);

for (i = 0; i < m; i++){

cin >> a >> b;

g->edge[a].push_back(b);

g->edge[b].push_back(a);

}

for (i = 1; i <= n; i++)

sort(g->edge[i].begin(), g->edge[i].end());

g->bfs(v);

}