TCS Graphs Quiz-1

Yes, Google Maps uses graphs to identify the shortest path but maybe some improved t path. They are definitely not using Dijkstra's algorithm to find the shortest path but maybe 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.

These are some application which uses Google map.

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

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

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

These are the two methods to represent the graph.

The complexity of an adjacency list and adjacency matrix of a graph G(V, E) is  O(n*m) and O(n+m).

Step1: Queue= { b }  or { b }

Queue={ b,a,c }  or { b,c,a }

Queue= { b,a, c,h } or { b,c,a,e }

Queue= { b,a,c,h, e } or { b,c,a,e }

Queue= { b,a,c,h, e,d } or { b,c,a,e,d }

Queue= {  b,a,c,h, e,d,g,f } or {b,c,a,e,d,f,g, h,}

Sequence= (bachedgf) or (bcaedfgh)

 b  is starting node 

Stack : 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

 because here we need to check every vertices and edges.