What are graph algorithms?
Graph algorithms answer questions about networks of nodes (vertices) joined by edges: what can be reached, what the cheapest route is, which links connect everything at the lowest total cost, and in what order dependent tasks can run. Eight classics cover most courses and interviews: BFS and DFS for exploring, Dijkstra and Bellman-Ford for shortest paths, Kruskal and Prim for minimum spanning trees, and topological sort and Kosaraju's algorithm for directed graphs.
Graph basics: vertices, edges, direction and weight
A graph G = (V, E) is a set of vertices joined by edges. Complexity is stated in terms of both: V is the number of nodes and E the number of edges, so O(V + E) means "proportional to the size of the graph".
- Undirected edges work both ways, like a friendship. Directed edges are arrows u → v, like a web link or "course A is a prerequisite of course B".
- Weighted edges carry a cost such as kilometres or minutes. In an unweighted graph every edge counts as 1, so the shortest path is the one with the fewest edges.
- A cycle is a path that returns to its start; a directed graph without one is a DAG. A graph is sparse when E is close to V and dense when E is close to V².
Adjacency list vs adjacency matrix
An adjacency matrix is a V × V table whose cell [u][v] holds the edge weight. It answers "is there an edge u → v?" in O(1) but always costs O(V²) memory, and listing a node's neighbours means scanning a whole row.
An adjacency list stores only the neighbours each node actually has: O(V + E) memory, and O(degree) to iterate a node's neighbours. Since nearly every algorithm here loops "for each neighbour v of u", a list keeps traversals at O(V + E) where a matrix makes them O(V²). Use a list unless the graph is dense or you need constant-time edge lookups. The Representation card beside the canvas shows both and highlights the row being scanned.
Which graph algorithm should I use?
- Reach everything, or fewest edges in an unweighted graph (grids, mazes, minimum moves) → breadth-first search (BFS).
- Explore deeply, detect cycles, find connected components, backtrack → depth-first search (DFS).
- Cheapest path from one source, all weights ≥ 0 → Dijkstra's algorithm.
- Cheapest path with negative weights, or detect a negative cycle → Bellman-Ford.
- Cheapest set of edges connecting every node (cables, pipes, clustering) → a minimum spanning tree: Kruskal for sparse graphs, Prim for dense ones.
- Order tasks that depend on each other (build order, course schedule) → topological sort, which also reports a dependency cycle.
- Groups of nodes that can all reach each other in a directed graph → strongly connected components.
Beyond this page: Floyd–Warshall for all-pairs shortest paths in O(V³), A* for a single target with a distance estimate, and max-flow for capacity problems.
How the algorithms relate
The eight algorithms are two traversal patterns plus a few twists. BFS is Dijkstra with every edge costing 1: with equal weights, a FIFO queue already hands out nodes in order of distance. Prim has Dijkstra's exact skeleton, but its key is the weight of the single edge into the tree instead of the total path length.
Kruskal sorts all edges and uses union-find to avoid cycles; Bellman-Ford is dynamic programming over the number of edges in a path. Topological sort has a BFS flavour (Kahn's algorithm) and a DFS flavour (reverse finishing order), and Kosaraju's SCC algorithm is two DFS passes, the second on the reversed graph. Learn BFS, DFS and the priority-queue loop well and the rest are small variations.
Using the visualizer
Generate a graph or draw your own (N adds nodes, E connects them, click a weight to edit it), pick an algorithm and press Run. Every step is recorded, so you can step backwards and scrub the timeline while the code panel highlights the matching line.
Time and space complexity
| Case | Time | Space | Why |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Each node is enqueued once; each adjacency list is scanned once. |
| DFS | O(V + E) | O(V) | Each node is visited once; the recursion can be V levels deep. |
| Dijkstra (binary heap) | O((V + E) log V) | O(V + E) | Every relaxation may push a heap entry costing O(log V). |
| Bellman-Ford | O(V · E) | O(V) | Up to V − 1 passes over every edge, plus one check pass. |
| Kruskal | O(E log E) | O(V + E) | Sorting the edges dominates; union-find is nearly O(1) per edge. |
| Prim (binary heap) | O(E log V) | O(V + E) | Each edge enters and leaves the heap at most once. |
| Topological sort (Kahn) | O(V + E) | O(V) | Each node is output once; each edge lowers one in-degree once. |
| SCC (Kosaraju) | O(V + E) | O(V + E) | Two DFS passes, plus a reversed copy of the graph. |
Frequently asked questions
What is the difference between BFS and DFS?
BFS explores level by level with a queue and finds fewest-edge paths in unweighted graphs. DFS goes as deep as possible with a stack (or recursion) and is the basis of cycle detection, topological sort and SCCs. Both run in O(V + E).
When should I use Dijkstra instead of BFS?
Use Dijkstra when edges have different non-negative weights. BFS minimizes the number of edges, which equals the cheapest cost only when every edge has the same weight.
What is the difference between Kruskal's and Prim's algorithm?
Both build a minimum spanning tree with the same total weight. Kruskal sorts all edges and merges trees with union-find, which suits sparse graphs; Prim grows one tree from a start node with a priority queue, which suits dense graphs.
Should I use an adjacency list or an adjacency matrix?
Use an adjacency list for most graphs: it takes O(V + E) memory and lets traversals run in O(V + E). An adjacency matrix (O(V²) memory) only pays off for dense graphs or when you need O(1) edge lookups.
What is a DAG?
A directed acyclic graph: every edge has a direction and no path leads back to where it started. DAGs are exactly the graphs that have a topological order, which is why they model dependencies and schedules.
Keep learning
- BFS Visualizer — Breadth-First SearchBreadth-first search explores a graph level by level with a queue and finds fewest-edge paths. Watch BFS run step by step, with code and O(V + E) analysis.
- Dijkstra's Algorithm VisualizerDijkstra's algorithm finds the shortest paths from one node in a graph with non-negative weights. Watch every relaxation step by step, with heap-based code.
- Kruskal's Algorithm VisualizerKruskal's algorithm builds a minimum spanning tree by adding the cheapest edges that don't form a cycle, using union-find. Watch it step by step, with code.
- Topological Sort VisualizerA topological sort orders the nodes of a DAG so every edge points forward. Watch Kahn's algorithm step by step, see why cycles block it, and get the code.
- Priority Queue VisualizerPriority queue visualizer: a binary heap always serves the top-priority item first. Watch insert, peek and extract in O(log n) and see how Dijkstra uses it.
- Queue VisualizerInteractive queue visualizer: watch enqueue and dequeue move the front and rear of an array queue, and see the wasted-space problem that circular queues fix.
Last updated