Graphs Quiz

8 questions12 minPass: 60%+10 XP on first pass

Adjacency lists, BFS vs DFS, islands, topological sort, union-find and Dijkstra.

Free account · see your score, answers and explanations, earn XP

Question 1
Why do graph traversals need a "visited" set when tree traversals usually don't?
Graphs can contain cycles, so without it you could loop foreverGraphs always have more nodesVisited sets make BFS faster than DFSTrees can't be traversed with DFS
Question 2
Which algorithm finds the fewest steps between two nodes in an UNWEIGHTED graph?
BFSDFSDijkstra is requiredBinary search
Question 3
How many islands are in this grid? (1 = land, 0 = water, connected up/down/left/right)
```
1 1 0 0
1 0 0 1
0 0 1 1
0 0 0 0
```
Question 4
"Can you finish all courses given prerequisites?" is the same as asking whether the directed graph…
Is a treeHas no cycleIs fully connectedHas an even number of edges
Question 5
In Kahn's algorithm (topological sort), which nodes enter the queue first?
Nodes with in-degree 0Nodes with the most edgesThe node with the smallest valueAll nodes at once
Question 6
Union-Find's union(a, b) returns False when a and b are already connected. In "Redundant Connection" this tells you…
The current edge creates a cycleThe graph is disconnectedThe graph is a treeNothing useful
Question 7
Dijkstra's algorithm works correctly only when edge weights are…
All equalNon-negativeNegativeIntegers
Question 8
In BFS, when should a node be marked visited to avoid adding it to the queue many times?
When it is pushed onto the queueWhen it is popped from the queueAfter the whole BFS finishesIt never needs marking