From given algorithms which one considered as best for finding the shortest-path:

• A) Bellman-Ford algorithm
• B) DFS
• C) BFS
• D) Dijkstra's algorithm

Dijkstra’s algorithm :

• A) Has both greedy and dynamic approach to compute single source shortest paths to all other vertices.
• B) Has both greedy and Dynamic approach to find all shortest paths
• C) Has greedy approach to find all shortest paths
• D) Has greedy approach to compute single source shortest paths to all other vertices

For _____________ graphs, there is no distinction between forward and back edges.

• A) medium
• B) large
• C) undirected
• D) directed

In strong components algorithm, vertices are sorted in________ order of finish times.

• A) Decreasing
• B) Any
• C) Increasing
• D) strong

If a subset of edges A is viable for building MST, it can not contain a/an _________.

• A) Edge
• B) Vertex
• C) Cycle
• D) Graph

In Kruskal's algorithm, the next ________ is not added to viable set A, if its adding induce a/an cycle.

• A) Cycle
• B) Vertex
• C) Edge
• D) Tree

The breadth-first-search algorithm is a shortest-path algorithm that works on__________graphs.

• A) Directed
• B) Un-directed
• C) Weighted
• D) Un-weighted

Once you enter a strong component, every vertex in the
component is _________.

• A) reachable
• B) reachable some times
• C) removed
• D) not reachable

In Timestamped DFS, No back edges means ___________.

• A) BFS
• B) DFS
• C) no cycles
• D) 1 cycle

The time complexity to compute Graph transpose G^T is (V+E), if you have ______________ for G.

• A) stack
• B) an adjacency list
• C) Array list
• D) complete list

Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best tree edge) when the __________ has relatively few __________.

• A) tree, edges
• B) tree, branches
• C) graph, edges
• D) graph, branches

Dijkstra’s algorithm is a simple________ algorithm for computing the single-source shortest-paths to all other vertices.

• A) Greedy
• B) Brute-Force
• C) Divide and conquer
• D) Bellman-Ford

What is the time complexity to extract a vertex from the priority queue in Prim’s algorithm?

• A) O(V+E)
• B) O(V)
• C) O(log E)
• D) O(log V)

A fully connected undirected graph of 5 nodes will have _________ edges.

• A) 15
• B) 4
• C) 5
• D) 10

In Prim's algorithm, If the color of a vertex is __________,then it is in S otherwise not.

• A) Black
• B) Gray
• C) White
• D) Blue

An un-weighted graph can be considered as a graph in which every edge has weight_______unit.

• A) 1
• B) 3
• C) 7
• D) 5