TRB PG Assistant - Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees Online Test (MCQ Quiz)

1. Which graph traversal algorithm explores as far as possible along each branch before backtracking?

A) Breadth-First Search (BFS) B) Depth-First Search (DFS) C) Dijkstra's Algorithm D) Prim's Algorithm

2. What data structure is typically used to implement Breadth-First Search (BFS)?

A) Stack B) Queue C) Heap D) Array

3. In Depth-First Search (DFS), what is the maximum depth of the recursion stack in a graph with V vertices and E edges?

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

4. Which algorithm finds the shortest path between two nodes in a weighted graph with non-negative edge weights?

A) Bellman-Ford Algorithm B) Floyd-Warshall Algorithm C) Dijkstra's Algorithm D) Kruskal's Algorithm

5. Dijkstra's algorithm guarantees finding the shortest path if all edge weights are:

A) Negative B) Positive C) Non-negative D) Zero

6. What is the time complexity of Dijkstra's algorithm using a binary heap for a graph with V vertices and E edges?

A) O(V^2) B) O(E log V) C) O(V log V) D) O(E + V)

7. The Bellman-Ford algorithm can find the shortest paths in a graph that contains:

A) Only positive edge weights B) Only non-negative edge weights C) Negative edge weights D) Only unit edge weights

8. What is the primary application of the Ford-Fulkerson method in graph algorithms?

A) Finding the shortest path B) Finding the minimum spanning tree C) Finding the maximum flow D) Detecting cycles

9. Which theorem states that the maximum flow in a network is equal to the capacity of a minimum cut?

A) Max-Flow Min-Cut Theorem B) Euler's Theorem C) Gomory-Hu Theorem D) Kuratowski's Theorem

10. A Minimum Spanning Tree (MST) of a connected, undirected graph is a subset of the edges that:

A) Connects all vertices and has the maximum possible total edge weight B) Connects all vertices and has the minimum possible total edge weight C) Forms a cycle with the minimum possible total edge weight D) Connects exactly half of the vertices with the minimum possible total edge weight

11. Which algorithm is commonly used to find a Minimum Spanning Tree (MST)?

A) Dijkstra's Algorithm B) Bellman-Ford Algorithm C) Prim's Algorithm D) Floyd-Warshall Algorithm

12. Prim's algorithm and Kruskal's algorithm both find the Minimum Spanning Tree of a graph. What is a key difference in their approach?

A) Prim's grows the MST from a single vertex, while Kruskal's adds edges in increasing weight order. B) Prim's requires a connected graph, while Kruskal's works on disconnected graphs. C) Prim's uses a queue, while Kruskal's uses a stack. D) Prim's handles negative edge weights, while Kruskal's does not.

13. What is the time complexity of Kruskal's algorithm using a Disjoint Set Union (DSU) data structure?

A) O(V^2) B) O(E log E) C) O(E log V) D) O(V + E)

14. In BFS, when we visit a node `u` and explore its neighbor `v`, if `v` has not been visited, `v` is marked as visited and added to the:

A) Stack B) Queue C) Priority Queue D) Set

15. DFS can be used to detect cycles in a directed graph by keeping track of:

A) Visited nodes and nodes currently in the recursion stack B) Only visited nodes C) Nodes at the current level D) The path length

16. What is the shortest path from a source node to itself in any graph?

A) Infinity B) Undefined C) 0 D) 1

17. The Floyd-Warshall algorithm computes the shortest paths between:

A) A single source and all other vertices B) Two specific vertices C) All pairs of vertices D) The source and the sink

18. What is the time complexity of the Floyd-Warshall algorithm for a graph with V vertices?

A) O(V^2) B) O(V^3) C) O(V log V) D) O(E log V)

19. Which of the following is NOT a characteristic of a flow network used in maximum flow problems?

A) A directed graph B) A source node `s` C) A sink node `t` D) A minimum capacity edge

20. An augmenting path in the context of maximum flow is a path from the source to the sink along which:

A) All edges have zero residual capacity B) There is some residual capacity C) All edges have negative residual capacity D) The path length is minimized

21. What does BFS find in an unweighted graph?

A) The path with the maximum number of edges B) The shortest path in terms of number of edges C) The path with the minimum total weight D) A cycle

22. In DFS, the 'discovery time' of a vertex is:

A) The time when the vertex is first visited B) The time when the DFS traversal finishes for that vertex C) The time when the vertex is removed from the recursion stack D) The total time spent exploring from that vertex

23. Which of the following is a key component of Dijkstra's algorithm to keep track of the shortest distance found so far from the source to each vertex?

A) A visited set B) A distance array C) A parent array D) A priority queue

24. If a graph contains a negative cycle reachable from the source, what will happen to Bellman-Ford algorithm?

A) It will terminate correctly and report the shortest paths. B) It will run indefinitely. C) It will detect the negative cycle and report it. D) It will produce incorrect shortest path distances.

25. The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method that uses which algorithm to find augmenting paths?

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

26. A cut in a flow network is a partition of the vertices into two sets, S and T, such that:

A) The source `s` is in T and the sink `t` is in S B) Both `s` and `t` are in S C) The source `s` is in S and the sink `t` is in T D) Both `s` and `t` are in T

27. Which property must a graph satisfy to have a Minimum Spanning Tree?

A) It must be a directed acyclic graph (DAG). B) It must be connected. C) It must contain at least one negative edge. D) It must be a complete graph.

28. Kruskal's algorithm relies on which data structure to efficiently check if adding an edge creates a cycle?

A) Hash Table B) Disjoint Set Union (DSU) C) Binary Search Tree D) Linked List

29. What is the primary goal of DFS in terms of graph exploration?

A) To find the shortest path in unweighted graphs. B) To explore as deeply as possible along each branch before backtracking. C) To find the minimum spanning tree. D) To compute the maximum flow.

30. In BFS, the 'level' of a node refers to:

A) Its depth in the recursion tree. B) Its distance (number of edges) from the source node. C) Its weight in the graph. D) Its topological order.

31. Which of the following statements about Dijkstra's algorithm is FALSE?

A) It works correctly for graphs with negative edge weights. B) It finds the shortest path from a single source to all other reachable vertices. C) It uses a priority queue to efficiently select the next vertex to visit. D) Its time complexity with a Fibonacci heap is O(E + V log V).

32. The Bellman-Ford algorithm performs V-1 iterations of relaxation. If, after V-1 iterations, any edge can still be relaxed, it indicates the presence of a:

A) Negative cycle B) Positive cycle C) Bridge D) Cut vertex

33. What is the residual capacity of an edge (u, v) in a flow network?

A) The capacity of the edge (u, v). B) The current flow through the edge (u, v). C) The capacity of the edge (u, v) minus the current flow through it. D) The capacity of the reverse edge (v, u).

34. Which of these is a greedy algorithm for finding a Minimum Spanning Tree?

A) DFS B) BFS C) Prim's Algorithm D) Bellman-Ford Algorithm

35. If a graph is disconnected, what can we say about its Minimum Spanning Tree?

A) It does not have an MST. B) It has an MST that connects all vertices. C) It has a Minimum Spanning Forest (MSF), which is a collection of MSTs for each connected component. D) The MST will have infinite weight.

36. The 'finish time' of a vertex in DFS is:

A) The time when the vertex is first discovered. B) The time when the algorithm finishes processing all descendants of the vertex. C) The time when the vertex is popped from the recursion stack. D) The total number of vertices visited after discovering this vertex.

37. Consider a directed graph. BFS is typically used to find shortest paths in:

A) Weighted graphs with non-negative weights. B) Weighted graphs with negative weights. C) Unweighted graphs. D) Graphs with negative cycles.

38. What is the purpose of the 'visited' array in both BFS and DFS?

A) To store the shortest distance from the source. B) To keep track of nodes that have already been explored to avoid cycles and redundant work. C) To store the parent of each node in the traversal tree. D) To prioritize nodes for visiting.

39. Which algorithm can solve the All-Pairs Shortest Path problem?

A) Dijkstra's Algorithm (run V times) B) Bellman-Ford Algorithm (run V times) C) Floyd-Warshall Algorithm D) BFS (run V times)

40. The Ford-Fulkerson method iteratively finds augmenting paths and increases the flow until:

A) The number of augmenting paths found reaches V. B) No more augmenting paths can be found from source to sink in the residual graph. C) The total flow equals the number of edges. D) All vertices have been visited.

41. What is the relationship between the capacity of a cut and the flow through that cut in a flow network?

A) Flow through a cut is always greater than the capacity of the cut. B) Flow through a cut is always less than the capacity of the cut. C) Flow through a cut is always equal to the capacity of the cut. D) Flow through a cut is not directly related to the capacity of the cut.

42. Prim's algorithm, when implemented with a binary heap, has a time complexity of:

A) O(V^2) B) O(E log V) C) O(V log V) D) O(E + V)

43. What characterizes the edges chosen by Kruskal's algorithm for an MST?

A) They are the edges incident to the vertex with the smallest degree. B) They are the edges with the smallest weights that do not form a cycle. C) They are the edges that connect the source to the furthest vertex. D) They are the edges that form the path with the maximum weight.

44. DFS is often used for topological sorting of:

A) Undirected graphs B) Graphs with negative edge weights C) Directed acyclic graphs (DAGs) D) Graphs with cycles

45. If `dist[v]` stores the shortest distance from the source to vertex `v`, and `w(u, v)` is the weight of edge (u, v), the relaxation step in Dijkstra's algorithm is:

A) If `dist[u] + w(u, v) < dist[v]`, then `dist[v] = dist[u] + w(u, v)` B) If `dist[u] + w(u, v) > dist[v]`, then `dist[v] = dist[u] + w(u, v)` C) If `dist[u] - w(u, v) < dist[v]`, then `dist[v] = dist[u] - w(u, v)` D) If `dist[v] < w(u, v)`, then `dist[v] = w(u, v)`

46. Which of the following is NOT a common application of BFS?

A) Finding the shortest path in unweighted graphs. B) Web crawlers. C) Garbage collection (e.g., Cheney's algorithm). D) Finding strongly connected components.

47. In the context of maximum flow, what does the residual graph represent?

A) The original graph with all capacities set to zero. B) A graph showing only the edges with current flow. C) A graph representing the remaining capacity available on edges and the possibility of 'undoing' flow. D) The graph with the minimum spanning tree.

48. Which algorithm is suitable for finding the shortest paths in a weighted graph that may contain negative edge weights but no negative cycles?

A) Dijkstra's Algorithm B) Prim's Algorithm C) Bellman-Ford Algorithm D) Kruskal's Algorithm

49. For a connected graph G = (V, E), what is the number of edges in any Minimum Spanning Tree?

A) V B) V - 1 C) E D) E - 1

Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees - Online Test

Test Results