BFS
(lib/graph/bfs.hpp)

• View this file on GitHub
• Last update: 2022-03-11 12:43:47+09:00
• Include: #include "lib/graph/bfs.hpp"

Verified with

• test/graph/bfs.test.cpp

Code

#pragma once
template<class veFi, class vFe >
void bfs(int n, int s, veFi g, vFe dtmn){
	vector<int>vis(n); vis[s] = 1;
	queue<int>q({ s });
	while(q.size()){
		int c = q.front(); q.pop();
		for(auto e: g(c))if(!vis[e.to])vis[e.to] = 1, dtmn(e), q.push(e.to);
	}
}

/*
* @title BFS
*/

#line 2 "lib/graph/bfs.hpp"
template<class veFi, class vFe >
void bfs(int n, int s, veFi g, vFe dtmn){
	vector<int>vis(n); vis[s] = 1;
	queue<int>q({ s });
	while(q.size()){
		int c = q.front(); q.pop();
		for(auto e: g(c))if(!vis[e.to])vis[e.to] = 1, dtmn(e), q.push(e.to);
	}
}

/*
* @title BFS
*/

Back to top page