Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees - Question Bank

1. 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
2. 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
3. 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.
4. 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.
5. 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)`
6. 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
7. 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.
8. 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)
9. 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.
10. 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.
11. 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)
12. 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.
13. 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.
14. 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.
15. 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.
16. 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
17. 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).
18. 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
19. 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).
20. 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.
21. 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.
22. 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
23. 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.
24. 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
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. 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.
27. 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
28. 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
29. 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
30. 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
31. 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
32. 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)
33. 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
34. What is the shortest path from a source node to itself in any graph?
A) Infinity
B) Undefined
C) 0
D) 1
35. 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
36. 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
37. 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)
38. 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.
39. 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
40. 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
41. 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
42. 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
43. 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
44. 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)
45. Dijkstra's algorithm guarantees finding the shortest path if all edge weights are:
A) Negative
B) Positive
C) Non-negative
D) Zero
46. 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
47. 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)
48. What data structure is typically used to implement Breadth-First Search (BFS)?
A) Stack
B) Queue
C) Heap
D) Array
49. 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
All Question Banks
E-Book Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees One Line Questions Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees Online Test Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees