A sample application of …………….. algorithm is to solve critical path problem, i.e. finding the longest path through a DAG.

Dijkstra algorithm is also called the  …………………. shortest path problem.

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

Graph

Time Complexity of DFS is? (V – number of vertices, E – number of edges)

Regarding implementation of Depth First Search using stacks, what is the maximum distance between two nodes present in the stack? (considering each edge length 1)

When the Depth First Search of a graph is unique?

A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?

Breadth First Search is equivalent to which of the traversal in the Binary Trees?

What are the appropriate data structures for following algorithms?

1) Breadth First Search

2) Depth First Search

3) Prim's Minimum Spanning Tree

4) Kruskal' Minimum Spanning Tree

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

……………… means, for all vertices, compute its reachability.

A digraph is strongly connected under what condition?

If you find yourself in maze the better traversal approach will be:

A dense undirected graph is:

………………… describe efficient algorithms for computing G^T from G, for both the adjacency list and adjacency matrix representations of G.