TCS NQT Graph Quiz – 1

For finding the shortest path.

Explanation: Yes, Google Maps uses graphs to identify the shortest, but may be some improved t path. They are definitely not using Dijkstra\'s algorithm to find the shortest path, but may be some improved version of dijkstra’s combined with other shortest path algorithms like A*. Dijkstra’s is just a starting point, and hence is not the most efficient algorithm. Different algorithms work differently in different use cases . hence algorithms need to be chosen intelligently based on the situation. I think that’s what Google Maps does.

Answer :: (D)

EXPLANATION :

All the Application which uses maps for their application uses graph data structure.

All the information of the friends that are add in your friends list and the suggestion you got so they are the friend of your friends in facebook so these all information are saved in the node and they are connected to each other via edges.

 It arranges the data in a sorted order and there exists a relationship between the data elements. So it’s a property of non linear data structure.

Graph is strongly connected if there is a path between any two pairs of vertices. For example following graph is strongly connected

These are the two methods to represent the graph.

Answer :: (C)

EXPLANATION :

Complexity for adjacency list = O(n+m)

Complexity for adjacency matrix = O(n*m)

Reason :

In a adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.

 because here we need to check every vertices and edges.

If, b  is starting node 

Stack will be like:

b/0/15

c/1/10

e/2/9

d/3/8

f/4/5

g/6/7

a/11/14

h/12/13

So node f take 5 time to visit

Method 1
start - {b}
{b,c,a}
{b,c,a,e}
{b,c,a,e,d}
{b,c,a,e,d,f,g} or {b,c,a,e,d,g,f}

Method 2
start - {b}
{b,a,c}
{b,a,c,h}
{b,a,c,h,e}
{b,a,c,h,e,d}
{b,a,c,h,e,d,f,g} or {b,a,c,h,e,d,g,f}