From d0980a6cc18d45f954d6f014c39398aaa095a694 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Wed, 1 Nov 2017 16:39:48 +0100 Subject: added bfs in c++ --- cpp/bfs.cc | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 69 insertions(+) create mode 100644 cpp/bfs.cc diff --git a/cpp/bfs.cc b/cpp/bfs.cc new file mode 100644 index 0000000..8174030 --- /dev/null +++ b/cpp/bfs.cc @@ -0,0 +1,69 @@ +#include +#include +#include + +#define WHITE 0 +#define GREY 1 +#define BLACK 2 +#define INF 99999 + +using namespace std; + +int checked[INF] = {WHITE}; +int d[INF] = {0}; +int f[INF] = {0}; +int t = 1; + +void bfs(const list lista[], int start) { + queue coda; + + int checked[999] = {WHITE}; + + coda.push(start); + + checked[start] = GREY; + while(!coda.empty()) { + int corrente = coda.front(); + coda.pop(); + + if(checked[corrente] == GREY) { + cout << corrente << ' '; + for(auto it = lista[corrente].begin(); it != lista[corrente].end(); ++it) { + coda.push(*it); + if(checked[*it] != BLACK) + checked[*it] = GREY; + } + checked[corrente] = BLACK; + } + } +} + +int main() { + int u, w; + int e; + cin >> e; + list lista[INF]; + for(int i = 0; i < e; ++i) { + cin >> u >> w; + lista[u].push_back(w); + } + + bfs(lista, 0); //0 is the start + + /* example: + http://pages.cs.wisc.edu/~mcw/cs367/lectures/images/bfs.gif + #input + 8 + 0 1 + 0 5 + 1 2 + 2 0 + 1 3 + 3 4 + 4 2 + 1 4 + #output + 0 1 5 2 3 4 + */ + return 0; +} -- cgit v1.2.3-18-g5258