Question

Write a pseudocode algorithm to search for a value in a graph (you can assume that each node v has a value field i.e. v.value). Compute the time complexity of your algorithm

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

We can simply use BFS to search for a value

BFS (G, s,x)                   //Where G is the graph and s is the source node
      let Q be queue.
      Q.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.
if(s.value==x) return true;
      mark s as visited.
      while ( Q is not empty)
           //Removing that vertex from queue,whose neighbour will be visited now
           v  =  Q.dequeue( )

          //processing all the neighbours of v  
          for all neighbours w of v in Graph G
               if w is not visited 
                        Q.enqueue( w )             //Stores w in Q to further visit its neighbour
/*---------------------------- */ if(w.value==x) return true;
                        mark w as visited.

The time complexity of BFS is O(V + E), where V is the number of nodes and E is the number of edges.

Kindly revert for any queries

Thanks.