[c++] BFS(Breadth First Search) 알고리즘

BFS 알고리즘은 너비를 우선으로 탐색하는 알고리즘 입니다.

즉, 현재 정점에 연결된 가까운 노드부터 탐구합니다.

주로 queue를 이용해서 구현합니다.

 

 

 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<vector<int>> graph(7, vector<int> ());
queue<int> q;
vector<bool> visit(7, false);
 
void dfs(int start) {
    visit[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        start = q.front();
        q.pop();
        
        printf("%d  ", start);
        
        for (int i = 0; i < graph[start].size(); i++) {
            if (!visit[graph[start][i]]) {
                visit[graph[start][i]] = true;
                q.push(graph[start][i]);
            }
        }
    }
}
 
int main(void){
    graph[1].push_back(2);
    graph[2].push_back(1);
    
    graph[1].push_back(3);
    graph[3].push_back(1);
    
    graph[2].push_back(4);
    graph[4].push_back(2);
    
    graph[2].push_back(3);
    graph[3].push_back(2);
    
    graph[2].push_back(5);
    graph[5].push_back(2);
    
    graph[3].push_back(4);
    graph[4].push_back(3);
    
    graph[3].push_back(6);
    graph[6].push_back(3);
    
    dfs(1);
    
    return 0;
}