BFS
Breadth first search uses queue.If we use adjacency list to store graph then the following code will implement the BFS:
list<int> adj[V]; // V is the number of vertices
vector<bool> visited(V, false);
queue<int> q;
void BFS(int s)// s is the starting index;
{
q.push_back(s);
while(!q.empth())
{
s = q.front();
cout << s << " ";
q.pop_front();
for(auto i = adj[s].begin();i != adj[s].end();i++)
{
if(!visited[*i])
{
visited[*i] = true;
q.push_back(*i);
}
}
}
}
However, this implementation will not be able to traverse a disconnected graph completely.To do so, we have to check every node by making it a starting node and BFS from that node.
for(int i = 0;i < V;i++)
{
if(!visited[i])
BFS(i);
}
DFS
DFS make use of stack. For than we don't have to use a separate stack, we can implement it using recursion. Following code shows implementation of DFS using assumptions taken while explaining BFS:
void DFS(int s)
{
visited[s] = true;
cout << s << " ";
for(auto i = adj[s].begin();i != adj[s].end();i++)
if(!visited[*i])
DFS(*i);
}
This implementation can also be made to traverse the whole graph, in case of disconnected graph, by using the iterative calls used in BFS.