[C++] queue로 BFS 구현하기

DFS는 vector로 구현도 해보고 문제도 몇개풀어봤으니 이제는 queue로 BFS를 구현해보려한다 DFS는 한 우물만 계속해서 파니까 쭉쭉 들어가기위해서 스택이 필요했고, BFS는 짧게짧게 갈 수 있는 모든 곳을 들러야하니까 FIFO(선입선출)인 큐가 필요하다

1. queue의 사용

• #include<queue>을 해줘야한다
• queue<int> Q;  : int형으로 Q라는 이름의 큐 선언
• Q.push(값) : 해당값을 큐 Q에 넣는다
• Q.pop() : 큐 Q의 front를 삭제한다
• Q.front() : 큐의 제일 앞 값을 리턴한다(삭제되지않음)
• Q.back() : 큐의 제일 마지막 값을 리턴한다(삭제되지않음)
• Q.size() : 큐 Q의 원소 개수를 리턴한다 
• Q.empty() : 큐가 비어있는지를 확인한다. 비어있으면 1 비어있지않으면 0을 리턴

2. queue로 BFS 구현하기 

일단.. BFS에 대해서 다시 생각해보면 길게 쭉 들어가는게 아니라 짧게짧게 한곳한곳을 거쳐가는 방식이다

만약 vertex 1에서 2, 3을 갈 수 있다고 하면 1이 큐에 들어간다음 pop되면서 갈 수 있는 2, 3이 큐에 들어간다 하나의 vertex가 큐에서 pop되면서 그 정점에서 갈 수 있는 곳들이 push되면 된다 아 그래프를 표현해야하니까 인접리스트를 만들기 위해 vector도 필요하겠구나

• 코드

#include<stdio.h>

#include<vector>

#include<queue>

#include<iostream>

using namespace std;

class Graph{

public:

vector<vector<int>> adj;

queue<int> Q;

int N;

Graph(){}

Graph(int n)

{

N = n;

adj.resize(n);

}

void makeEdge(int u, int v)

{

adj[u].push_back(v);

adj[v].push_back(u);

}

void BFS()

{

vector<bool> visited(N, false);

Q.push(0); //0에서 시작한다고 가정(모든 vertex가 연결되어있다면)

visited[0]=true;

vector<int>::const_iterator next;

while(Q.empty()!=true)

{

int curr = Q.front();

Q.pop();

printf("%d ", curr);

for(next=adj[curr].begin() ; next !=adj[curr].end() ; next++)

{

if(visited[*next]!=true){

visited[*next]=true;

Q.push(*next);

}

}

}

}

};

int main()

{

int i;

int n, e, u, v;

scanf("%d %d", &n, &e);

Graph G(n);

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

{

scanf("%d %d", &u, &v);

G.makeEdge(u, v);

}

G.BFS();

}