BfS code for short coding contests.

general
,
1

I just studied BFS. I am trying to find short and simple BFS code/snippet for short programming contests.If anyone has shortest and simplest implementation of BFS, let me know.

1 Like
2

I feel that you are confused, like bfs, and dfs are the shortest codes you will find in graphs, both are just 4- 5 lines

dfs(int v)
{
   visited[v] = 0;
   for(auto u : adj[v])
     if(!visited[u])dfs(u); 
}

bfs(int src)
{
   queue.push(src);
   visited[src] = true;
   while(!q.empty())
   {
      int v = q.front();
      for(auto u : adj[v])
      if(!visited[u])
      {
         queue.push(u);
         visited[u] = true;
      }
   }
}
3

Ps : if you don’t use c++ 11 or 14, then for(auto u : adj[v]) can be written as

for(int i=0;i<adj[v].size();++i)

and u can be accessed as adj[v][i]

4

Yeah, DFS code is merely 3-4 lines. I am trying to find a BFS code as short as DFS but i don’t think that i will find a bfs code smaller and simper than the one you posted!

5

@devarshi09 dfs is actually rarely used, and is generally used to find levels of node in a tree, I once found a very simple and shorter code to find levels using dfs, which means we can ignore use bfs at all. Here is the code I was talking about.(function can be called with depth 0 dfs(src,0) )

dfs(int v, int depth)
{
  visited[v] = true;
  level[v] = depth;
  for(auto u : adj[v])
    if(!visited[i]) dfs(u, depth + 1);
}
6

@pshishod2645 So, that means what bfs does, can be done by dfs also? Can’t the problem be created such that it can only be solved with the help of bfs and not dfs?

7

@devarshi09 Yeah, exactly. Don’t know if dfs fails somewhere, and using bfs is a compulsion. but until you find that problem sticking to bfs seems a good idea :slight_smile:

8

bfs is preferred over recursive dfs in case of huge constraints like 1e6 elements where stack size is an issue. Maybe consider iterative bfs and dfs.

9

@taran_1407 Noted!