Skip to content

Instantly share code, notes, and snippets.

@jatindhankhar
Last active February 23, 2022 22:26
Show Gist options
  • Save jatindhankhar/475763812e34edf3903d to your computer and use it in GitHub Desktop.
Save jatindhankhar/475763812e34edf3903d to your computer and use it in GitHub Desktop.
Simple BFS implementation in modern C++
//Modified version of http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
# include <iostream>
# include <algorithm>
# include <vector>
# include <list>
using namespace std;
class Graph
{
vector< vector<int> > Edge;
vector<unsigned char> visited; //We can use vector<bool>, but it's slow and broken :( , CPP's byte array http://stackoverflow.com/questions/10077771/what-is-the-correct-way-to-deal-with-medium-sized-byte-arrays-in-modern-c
public:
Graph(int V)
{
Edge.resize(V);
visited.resize(V);
}
void add_edge(int v,int w)
{
Edge[v].push_back(w);
}
void BFS(int s)
{
for(auto i : visited) i = false;
list<int> q;
visited[s] = true;
q.push_back(s);
while (!q.empty())
{
s = q.front();
cout<<s<<" ";
q.pop_front();
for(auto i : Edge[s])
{
if(!visited[i])
{
visited[i] = true;
q.push_back(i);
}
}
}
}
};
int main()
{
Graph g(6);
g.add_edge(0,1);
g.add_edge(0,2);
g.add_edge(1,2);
g.add_edge(2,0);
g.add_edge(2,3);
g.add_edge(3,3);
int v;
cout<<"Enter vertex from where to perform BFS"<<endl;
cin>>v;
g.BFS(2);
cout<< (char)true;
}
@Arterim7299
Copy link

HEY it won't work unless the header files of and is provided
👎
:(

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment