Question

We can use breadth-first search to find the length of longest simple path in the BFS tree
starting at s by the simple method of checking each v.d value at the end of the algorithm. BFS is
Θ(|V | + |E| and this adds only Θ(|V |) work.
Find an even easier approach that adds only constant time (Θ(1)) work via a simple modification to
the BFS algorithm.

Answer 1

If a graph G is given, then we mostly use the current vertex and G to do BFS.

If we use a count parameter as well doing bfs then we can find the longest path in Θ(1) work.

BFS (G, s)                   //Where G is the graph and s is the source vertex
      let Q be queue.
      Q.enqueue( s, 1 ) //Inserting s in queue and the size of path till s
      mark s as visited.
      while ( Q is not empty)
           //Removing that vertex from queue
           v  =  Q.dequeue( )
           maxpath= max(maxpath,v.dist)     // v.dist gives the length of path till this vertex
          //processing all the neighbours of v  
          for all neighbours n of v in Graph G
               if w is not visited 
                        Q.enqueue( w , v.dist+1)    //Stores w in Q to further visit its neighbour
                        mark w as visited.

maxpath stores the length of the maximum path of the graph i.e. our solution.

Rather than maintaining queue of vertices in BFS, we maintain queue of pair of vertice and the length of path till it.