A graph is a set of nodes connected by edges. The core algorithms are: breadth-first search (BFS) for exploring level by level and shortest paths in unweighted graphs; depth-first search (DFS) for connectivity, cycle detection and topological sorting; Dijkstra's algorithm for shortest paths with non-negative weights; and union-find plus minimum spanning tree algorithms for grouping and cheap connections. Most graph problems become easy once you see which of these they are.
Where do graphs appear?
Anything with connections is a graph: road and railway networks, flight routes, social networks (who follows whom), web pages and their links, course prerequisites, package dependencies, computer networks, and knowledge graphs used by search engines. Recommendation systems model users and items as graphs, and modern AI includes graph neural networks. Learning to model a problem as a graph is often the hardest and most valuable step.
How are graphs represented?
| Representation | Space | Check edge u–v | List neighbours | Best for |
|---|---|---|---|---|
| Adjacency list | O(V + E) | O(degree) | O(degree) | Most real, sparse graphs |
| Adjacency matrix | O(V²) | O(1) | O(V) | Small or dense graphs |
| Edge list | O(E) | O(E) | O(E) | Kruskal's algorithm, input formats |
V is the number of nodes and E the number of edges. Graphs can be directed or undirected, weighted or unweighted, and cyclic or acyclic; each property changes which algorithms apply.
Arithmetic: 10,000² = 100,000,000 vs 10,000 + 2 × 50,000 = 110,000.
How does breadth-first search work?
BFS starts at a node, visits all its neighbours, then their neighbours, and so on, using a queue and a visited set. Because it explores in order of distance (number of edges), the first time it reaches a node is along a shortest path in an unweighted graph. Uses: shortest route by number of hops, "degrees of separation" in a social network, finding the nearest open item in a grid, and level-order tree traversal. Time: O(V + E).
How does depth-first search work?
DFS goes as deep as possible along one path before backtracking, using recursion or an explicit stack. It's the natural tool for exploring everything reachable, counting connected components (islands in a grid), detecting cycles, finding paths in mazes and producing topological orders. Time: O(V + E). In Python, deep recursion can hit the default recursion limit on large graphs, so iterative DFS with a stack is safer.
How does Dijkstra's algorithm find shortest paths?
When edges have weights (distances, times, costs), BFS no longer finds the shortest path. Dijkstra's algorithm keeps a tentative distance for every node, starting at 0 for the source and infinity elsewhere. It repeatedly takes the unvisited node with the smallest tentative distance (using a priority queue), finalises it, and relaxes its edges: if going through this node gives a neighbour a shorter distance, update it. With a binary heap it runs in O((V + E) log V). It requires non-negative weights; with negative edges, use Bellman-Ford. Navigation apps use far more advanced variants with precomputation, but the core idea is the same.
What is topological sort?
In a directed acyclic graph (DAG), a topological order lists nodes so that every edge points forward: each task comes after its prerequisites. Kahn's algorithm repeatedly removes nodes with no incoming edges; a DFS-based method adds nodes after exploring all their descendants and reverses the result. If not all nodes can be ordered, there's a cycle, such as course A requiring B and B requiring A. Build tools, spreadsheet recalculation, data pipelines and package managers all rely on it.
Which other algorithms are worth knowing?
| Algorithm | Solves | Complexity (typical) |
|---|---|---|
| Union-find (disjoint set) | Grouping, "are these connected?", cycle detection in undirected graphs | Nearly O(1) per operation |
| Kruskal's / Prim's | Minimum spanning tree: connect all nodes at least total cost | O(E log E) |
| Bellman-Ford | Shortest paths with negative weights; detects negative cycles | O(V × E) |
| Floyd-Warshall | All-pairs shortest paths on small graphs | O(V³) |
| A* search | Shortest path guided by a heuristic, as in games and maps | Depends on heuristic |
How do you choose the right algorithm?
- Unweighted shortest path: BFS.
- Weighted, non-negative: Dijkstra.
- Negative weights: Bellman-Ford.
- Ordering with dependencies: topological sort.
- Connected groups, merging sets: DFS/BFS or union-find.
- Cheapest way to connect everything: minimum spanning tree.
- Grid problems: treat each cell as a node with up to four neighbours, then apply BFS or DFS.
What does a worked example look like?
A learning platform has course prerequisites: Python → DSA, Python → Databases, DSA → System Design, Databases → System Design, and DSA → Machine Learning. Kahn's algorithm finds Python as the only course with no prerequisites, removes it, then finds DSA and Databases free, then System Design and Machine Learning. One valid order: Python, DSA, Databases, Machine Learning, System Design. If someone accidentally added "System Design → Python", the algorithm would stop with nodes left over, revealing the cycle. This is exactly how curricula and build systems check dependencies.
What mistakes are common?
- Forgetting the visited set, so cycles cause infinite loops.
- Using BFS for weighted shortest paths.
- Running Dijkstra with negative weights.
- Marking nodes visited at the wrong time in BFS (mark when enqueuing, not when dequeuing, to avoid duplicates).
- Building an adjacency matrix for a huge sparse graph and running out of memory.
How do graphs show up in AI systems?
Knowledge graphs store facts as nodes and relationships, and search engines and some RAG systems use them to answer questions that need connected facts. Recommendation systems treat users and items as a graph and use random walks or graph neural networks to find related items. Route planning, logistics and delivery assignment are graph optimisation problems at heart. Even a neural network is a directed acyclic graph of operations, and deep learning frameworks run a topological sort of that graph to decide the order of computation and backpropagation. Learning classic graph algorithms is therefore directly useful in AI work, not just in interviews.
How do you model a problem as a graph?
Ask three questions: what are the nodes (cities, people, tasks, grid cells, states of a puzzle), what are the edges (roads, friendships, dependencies, moves), and do edges have direction or weight? Many puzzle problems become BFS once you see that each state, such as a combination-lock setting or a word in a word ladder, is a node, and each allowed move is an edge. Once the graph is clear, the algorithm usually follows from the table above.
How are graph questions asked in interviews?
Common formats: count islands in a grid (DFS/BFS), find whether all courses can be finished (cycle detection and topological sort), shortest path in a maze (BFS) or a weighted network (Dijkstra), clone a graph, and detect whether two nodes are connected after a series of unions (union-find). Interviewers look for a clear graph model, the right algorithm with its complexity, and careful handling of visited nodes and edge cases such as disconnected graphs or self-loops.
How should you practise?
Implement BFS, DFS, Dijkstra, Kahn's topological sort and union-find from scratch in Python, then solve grid, island-counting, course-schedule and network-delay problems. Graphs are part of Program Zero's ten-week DSA course; continue with dynamic programming and the DSA preparation plan.