QuizzesGraphs & BFS/DFS
advanced
dsa

Graphs & BFS/DFS

Adjacency representations, shortest paths, cycle detection, topological sort, and connected components.

30 minutes 10 questions Pass at 70%
Time Limit
30 minutes - timer starts when you begin
Change Answers Freely
Revisit and change any answer before submitting
Full Review After Submit
Correct answers and explanations shown for every question
Auto-submit on timeout
Quiz submits automatically when time runs out

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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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