Advance

Graphs Data Structure Questions

DSA

10 questions

Please login before attempting the quiz

Question 1

What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?

It can detect negative weight cycles.
It is more efficient for sparse graphs.
It only requires a single source vertex as input.
It can handle graphs with negative edge weights.

Question 2

What is a potential drawback of using A* search in practice?

It can be computationally expensive for large graphs with complex heuristics.
It is not guaranteed to find a solution even if one exists.
It always requires an admissible heuristic, which can be difficult to define.
It can only be applied to problems in two-dimensional space.

Question 3

Consider a network flow graph with a source 's' and sink 't'. Applying the Ford-Fulkerson algorithm results in a maximum flow of 10 units. Now, we increase the capacity of an edge on the shortest augmenting path by 2 units. What is the maximum possible flow after this modification?

10 units
12 units
Cannot be determined
11 units

Question 4

In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?

V
V - 1
E - 1
E

Question 5

What is the minimum number of edges that need to be removed from a complete graph with 'n' vertices to make it acyclic (i.e., having no cycles)?

1
n/2
n - 1
n

Question 6

In the context of shortest path algorithms, what is 'relaxation'?

Removing edges that cannot contribute to the shortest path.
Reducing the priority of a node in the priority queue.
Updating the distance to a node if a shorter path is found.
Transforming a directed graph into an undirected graph.

Question 7

How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?

It removes all negative edges from the graph.
It reweights the edges using a shortest path potential function.
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It adds a large constant to all edge weights to make them positive.

Question 8

What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?

O(V + E), where V is the number of vertices and E is the number of edges
It depends on the heuristic function and can be exponential in the worst case.
O(E log V), where V is the number of vertices and E is the number of edges
O(V^2), where V is the number of vertices

Question 9

What is the time complexity of the Edmonds-Karp algorithm when using a Breadth-First Search (BFS) to find augmenting paths in a network flow graph with 'V' vertices and 'E' edges?

O(V^2 * E)
O(V * E)
O(E^2 * V)
O(V + E)

Question 10

In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?

O(V^2)
O(V log V)
O(V^3)
O(E log V)