1
GATE CSE 2016 Set 1
Numerical
+1
-0
Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is ________________.

2
GATE CSE 2014 Set 1
+1
-0.3
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
A
$$\Theta(n)$$
B
$$\Theta(n+m)$$
C
$$\Theta(n^2)$$
D
$$\Theta(m^2)$$
3
GATE CSE 2014 Set 3
Numerical
+1
-0
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
4
GATE CSE 2014 Set 2
+1
-0.3
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing
A
the shortest path between every pair of vertices.
B
the shortest path from W to every vertex in the graph.
C
the shortest paths from W to only those nodes that are leaves of T.
D
the longest path in the graph.
GATE CSE Subjects
EXAM MAP
Medical
NEET