Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees - One Line Questions

1. Which of the following is NOT a characteristic of a flow network used in maximum flow problems? — A minimum capacity edge
2. The Floyd-Warshall algorithm computes the shortest paths between: — All pairs of vertices
3. 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 distance array
4. An augmenting path in the context of maximum flow is a path from the source to the sink along which: — There is some residual capacity
5. Which algorithm finds the shortest path between two nodes in a weighted graph with non-negative edge weights? — Dijkstra's Algorithm
6. Which graph traversal algorithm explores as far as possible along each branch before backtracking? — Depth-First Search (DFS)
7. A Minimum Spanning Tree (MST) of a connected, undirected graph is a subset of the edges that: — Connects all vertices and has the minimum possible total edge weight
8. The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method that uses which algorithm to find augmenting paths? — BFS
9. Which of these is a greedy algorithm for finding a Minimum Spanning Tree? — Prim's Algorithm
10. Which algorithm is commonly used to find a Minimum Spanning Tree (MST)? — Prim's Algorithm
11. Which algorithm is suitable for finding the shortest paths in a weighted graph that may contain negative edge weights but no negative cycles? — Bellman-Ford Algorithm
12. Which algorithm can solve the All-Pairs Shortest Path problem? — Floyd-Warshall Algorithm
13. What is the primary application of the Ford-Fulkerson method in graph algorithms? — Finding the maximum flow
14. Which of the following is NOT a common application of BFS? — Finding strongly connected components.
15. What is the relationship between the capacity of a cut and the flow through that cut in a flow network? — Flow through a cut is always equal to the capacity of the cut.
16. Kruskal's algorithm relies on which data structure to efficiently check if adding an edge creates a cycle? — Disjoint Set Union (DSU)
17. 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: — If `dist[u] + w(u, v) < dist[v]`, then `dist[v] = dist[u] + w(u, v)`
18. What is the shortest path from a source node to itself in any graph? — 0
19. If a graph is disconnected, what can we say about its Minimum Spanning Tree? — It has a Minimum Spanning Forest (MSF), which is a collection of MSTs for each connected component.
20. Which property must a graph satisfy to have a Minimum Spanning Tree? — It must be connected.
21. If a graph contains a negative cycle reachable from the source, what will happen to Bellman-Ford algorithm? — It will detect the negative cycle and report it.
22. Which of the following statements about Dijkstra's algorithm is FALSE? — It works correctly for graphs with negative edge weights.
23. In BFS, the 'level' of a node refers to: — Its distance (number of edges) from the source node.
24. Which theorem states that the maximum flow in a network is equal to the capacity of a minimum cut? — Max-Flow Min-Cut Theorem
25. Dijkstra's algorithm guarantees finding the shortest path if all edge weights are: — Non-negative
26. 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: — Negative cycle
27. What is the time complexity of Dijkstra's algorithm using a binary heap for a graph with V vertices and E edges? — O(E log V)
28. What is the time complexity of Kruskal's algorithm using a Disjoint Set Union (DSU) data structure? — O(E log V)
29. What is the time complexity of the Floyd-Warshall algorithm for a graph with V vertices? — O(V^3)
30. Prim's algorithm, when implemented with a binary heap, has a time complexity of: — O(E log V)
31. In Depth-First Search (DFS), what is the maximum depth of the recursion stack in a graph with V vertices and E edges? — O(V)
32. The Bellman-Ford algorithm can find the shortest paths in a graph that contains: — Negative edge weights
33. Prim's algorithm and Kruskal's algorithm both find the Minimum Spanning Tree of a graph. What is a key difference in their approach? — Prim's grows the MST from a single vertex, while Kruskal's adds edges in increasing weight order.
34. What data structure is typically used to implement Breadth-First Search (BFS)? — Queue
35. 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: — Queue
36. What is the residual capacity of an edge (u, v) in a flow network? — The capacity of the edge (u, v) minus the current flow through it.
37. The Ford-Fulkerson method iteratively finds augmenting paths and increases the flow until: — No more augmenting paths can be found from source to sink in the residual graph.
38. In the context of maximum flow, what does the residual graph represent? — A graph representing the remaining capacity available on edges and the possibility of 'undoing' flow.
39. What does BFS find in an unweighted graph? — The shortest path in terms of number of edges
40. A cut in a flow network is a partition of the vertices into two sets, S and T, such that: — The source `s` is in S and the sink `t` is in T
41. The 'finish time' of a vertex in DFS is: — The time when the vertex is popped from the recursion stack.
42. In DFS, the 'discovery time' of a vertex is: — The time when the vertex is first visited
43. What characterizes the edges chosen by Kruskal's algorithm for an MST? — They are the edges with the smallest weights that do not form a cycle.
44. What is the primary goal of DFS in terms of graph exploration? — To explore as deeply as possible along each branch before backtracking.
45. What is the purpose of the 'visited' array in both BFS and DFS? — To keep track of nodes that have already been explored to avoid cycles and redundant work.
46. DFS is often used for topological sorting of: — Directed acyclic graphs (DAGs)
47. For a connected graph G = (V, E), what is the number of edges in any Minimum Spanning Tree? — V - 1
48. DFS can be used to detect cycles in a directed graph by keeping track of: — Visited nodes and nodes currently in the recursion stack
49. Consider a directed graph. BFS is typically used to find shortest paths in: — Unweighted graphs.
All One Line Questions
E-Book Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees Online Test Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees Question Bank Graph Algorithms - BFS, DFS, shortest paths, maximum flow, minimum spanning trees