____________ technique is look like propagating wave-front outward.

• A) Breadth First Traversal
• B) Depth First Traversal
• C) Time Stamp Traversal
• D) Generic Traversal

____________ components are not affected by reversal of all edges in terms of vertices reachability.

• A) Weakly connected
• B) Strongly connected
• C) First two
• D) Last two

There are no ________ edges in undirected graph.

• A) Forward
• B) Cross
• C) Both forward and back
• D) Back

In Prim's algorithm, we will make use of_______________.

• A) Priority Queue
• B) Array
• C) List
• D) Stack

The component digraph is necessarily _____________.

• A) cyclic
• B) straight
• C) acyclic
• D) strong

The ________ given by DFS allow us to determine whether the graph contains any cycles.

• A) Topological sort
• B) Time stamps
• C) BFS traversing
• D) Order

Which of the following statement is true.

• A) Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best Tree edge) when the graph has relatively few edges.
• B) Kruskal algorithm is multiple source technique for finding MST.
• C) Both I and II
• D) Kruskal’s algorithm is used to find minimum spanning tree of a graph, time complexity of this algorithm is O(EV)

Overall Running time of Prim's algorithm is _______.

• A) Θ(ElogE)
• B) Θ((V+E)logV)
• C) Θ((V+E)logE)
• D) Θ(ElogV)

In Dijkstra’s algorithm the estimated value of source vertex d[s] is:

• A) Equal to 1
• B) Equal to 0
• C) Greater than 1
• D) Greater than 0

Which of the following is used in the data structure for implementing Dijkstra’s Algorithm?

• A) Stack’s
• B) Max heap
• C) Circular queue
• D) Priority queue

In Timestamped DFS-cycles lemma, if edge (u, v) is a back edge, then _________

• A) $${\text{f[u]}} > {\text{f[v]}}$$
• B) $${\text{f[u]}} \leqslant {\text{f[v]}}$$
• C) $${\text{f[u]}} \geqslant {\text{f[v]}}$$
• D) $${\text{f[u]}} < {\text{f[v]}}$$

A free tree with n vertices have exactly ________ edges.

• A) n - 1
• B) 1
• C) n + 1
• D) n

Prim’s algorithm is based on ---------------- strategy.

• A) Exponential
• B) Divide and Conquer
• C) Dynamic programming
• D) Greedy

For each vertex u ϵ (V − S) ,we associate a key ____________.

• A) key[u]
• B) key[v]
• C) key[v-s]
• D) key[s]

Problems such as the shortest route between cities can be solved efficiently by modeling the road map as a______________.

• A) Linked list
• B) Tree
• C) Graph
• D) Stack

Finding the faster result of the shortest path from u to v for every pair of vertices u and v we use__________.

• A) Two-pairs shortest-paths problem
• B) both I and II
• C) All-pairs shortest-paths problem
• D) Single-pairs shortest-paths problem

In Dijkstra’s algorithm, initially the estimated value from source vertex to any vertex v is:

• A) Zero (0)
• B) Minus one (-1)
• C) Infinity (∞)
• D) One (1)

In strong components algorithm, first of all DFS is run for getting _______ times of vertices.

• A) Middle
• B) Finish
• C) Both start & finish
• D) Start

The process of updating estimates in Dijkstra’s algorithm is called_____________.

• A) Relaxation
• B) Insertion
• C) Amendment
• D) Updating

In Prim’s algorithm, If there is no edge from u to a vertex in S, we set the key value to___________.

• A) 0
• B) -1
• C) 1
• D) ∞