Graphs & BFS/DFS
Adjacency representations, shortest paths, cycle detection, topological sort, and connected components.
Questions in this quiz
10 questions on Graphs & BFS/DFS. Work through them here, then start the quiz to answer them and see your score.
1.What is the space complexity of adjacency list vs adjacency matrix for a graph with V vertices and E edges?
- ABoth O(V + E)
- BList: O(V²); Matrix: O(V + E)
- CBoth O(V²)
- DList: O(V + E); Matrix: O(V²)
2.BFS finds the shortest path in terms of what?
- AMinimum total edge weight
- BAny graph including negative weights
- CFewest nodes visited
- DFewest edges (hops) — valid when all edge weights are equal
3.What does this code count for grid = [[1,1,0],[0,1,0],[1,1,1]] using 4-directional DFS that marks visited cells as 0?
int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { dfs(grid, i, j); // marks all connected 1s as 0 count++; } } } System.out.println(count);- A1
- B2
- C3
- D4
4.What is topological sort and when can it be applied?
- ASorting nodes by their integer value in ascending order
- BSorting graph edges by weight
- COrdering nodes of a DAG such that for every directed edge u→v, u appears before v
- DA BFS starting simultaneously from all nodes
5.What is the time complexity of Dijkstra's algorithm with a min-heap (priority queue)?
- AO(E log V)
- BO(V log V)
- CO((V + E) log V)
- DO(V²)
6.Cycle detection in an undirected graph vs a directed graph — what is the difference?
- ABoth require topological sort
- BUndirected: DFS back edge to any visited non-parent node = cycle; Directed: DFS back edge to an "in-stack" node = cycle
- CBoth use the exact same DFS algorithm
- DUndirected: BFS only; Directed: DFS only
7.What does BFS print for graph {0:[1,2], 1:[3], 2:[3], 3:[]}, starting from node 0?
Queue<Integer> q = new LinkedList<>(); boolean[] visited = new boolean[4]; q.offer(0); visited[0] = true; while (!q.isEmpty()) { int node = q.poll(); System.out.print(node + " "); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; q.offer(neighbor); } } }- A0 3 2 1
- B0 1 2 3
- C0 1 3 2
- D0 2 1 3
8.What is a bipartite graph and how do you check if a graph is bipartite?
- AA directed graph with exactly two strongly connected components
- BA graph with no cycles
- CA graph where nodes can be 2-coloured such that no two adjacent nodes share the same colour — check with BFS/DFS colouring
- DA graph with exactly two nodes
9.Why must you mark a node as visited BEFORE enqueuing it in BFS (not after dequeuing)?
- ABFS requires nodes to be unmarked when first dequeued
- BMarking before enqueue prevents the same node from being enqueued multiple times via different paths
- CIt makes no difference — both work correctly
- DMarking after dequeue is faster
10.What is the difference between a connected component (undirected) and a strongly connected component (directed)?
- AStrongly connected applies to undirected; connected to directed
- BConnected component: any two nodes can reach each other (undirected); Strongly connected: every node can reach every other via directed edges
- CThey are the same concept
- DConnected components only exist in DAGs