edited by
1,102 views
2 votes
2 votes

Consider an unweighted undirected graph connected with ‘$n$’ vertices and ‘$m$’ edges.

What is the worst case time complexity to check if two particular vertices ‘$x$’ and ‘$y$’ are present in graph; and, if present, how is the minimum distance between them calculated?

  1.   $O\left ( m+ n\log m \right )$
  2.   $O\left ( n \right )$
  3.   $O\left ( n\log n \right )$
  4.   $O\left ( n+m \right )$
edited by

1 Answer

Best answer
8 votes
8 votes
We can represent this an unweighted undirected graph connected with ‘$n$’ vertices and '$m$' edges into an adjacency list representation.

we can make an array of pointers of n vertices and then take a respective edge between two vertices.

We can find two vertices  '$x$' and '$y$' vertices in just $O$$\left ( n \right )$ time.

And then Breadth first search is an algorithm which is used to find the shortest path in an unweighted undirected graph of '$n$' vertices and '$m$' edges, its complexity will be $O$$\left ( n+m \right )$

so overall complexity of this task would be : $O$$\left ( n+m \right )$

option $D$
edited by
Answer:

Related questions

3 votes
3 votes
1 answer
1
Bikram asked May 14, 2017
297 views
What is the worst case time complexity to calculate the depth of a directed acyclic graph (DAG) with ‘$V$’ vertices and ‘$E$’ edges?$O\left ( V+E \right )$$O\left...
4 votes
4 votes
3 answers
3