What this topic covers
19 subtopics- Shortest paths7
- BFS6
- Basics5
- Cycles3
- Minimum spanning trees3
- Representations3
- Topological sort3
- Bridges and articulation points2
- DFS2
- Grid graphs2
- All-pairs shortest paths1
- Bipartite graphs1
Show all 19 subtopics
- Connected components1
- DAG dynamic programming1
- Euler paths1
- Graph colouring1
- Graph copying1
- Strongly connected components1
- Union-find1
- Beginner 15
- Intermediate 15
- Advanced 15
About this topic
Graphs model networks, maps, dependencies and social connections. Most questions come down to a few algorithms: BFS (queue, level by level – shortest paths in unweighted graphs), DFS (stack or recursion – cycles, components, topological order), Dijkstra (priority queue – shortest paths with non-negative weights) and Kruskal / Prim (minimum spanning trees). Traversal orders depend on the order neighbours are visited, so every question states it. The graphs are drawn, and every answer was computed by running the algorithm.
Free preview
Sample questions
Try each one first, then open the answer for the explanation and why the other options are wrong.
What is the BFS order starting from A (neighbours visited in alphabetical order)?
Show answer and explanation
Explanation
BFS finishes each distance before the next: distance 1 = B, D; distance 2 = C, E (from B; E is first discovered by B); distance 3 = F.
Why the other options are wrong
- AThat is DFS.
- BThat is alphabetical order, not BFS.
- CNeighbours of A are taken alphabetically: B before D.
Kahn's algorithm repeatedly removes a vertex with in-degree 0, always choosing the smallest such vertex. What order does it produce?
Show answer and explanation
Explanation
Sources are 4 and 5. Removing 4 leaves 0 and 1 with one incoming edge each; removing 5 frees 2 and 0, and 0 is smaller. Then 2, which frees 3, which frees 1. Every edge goes left to right in the result.
Why the other options are wrong
- A0 has incoming edges from 5 and 4.
- BAfter 5 is removed, 0 (smaller than 2) is available.
- DA valid order, but not the smallest-first one.
This directed graph has a negative edge. What is the shortest distance from S to C?
The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
S → B → A costs 5 − 3 = 2, cheaper than S → A (4); then A → C gives 4. Dijkstra would finalise A at 4 before seeing the negative edge. Bellman–Ford relaxes all edges V − 1 times.