Graph Algorithms

Breadth-first search (BFS) vs Depth-first search (DFS) vs DijkstragraphThree algorithms, three different shapes of graph problem. Breadth-first search (BFS)graphBreadth-first search explores a graph level by level using a queue. Depth-first search (DFS)graphDepth-first search explores as deep as possible before backtracking, using a stack (often the call stack). DijkstragraphDijkstra's algorithm finds shortest paths from a source in a graph with non-negative edge weights.

Traversal and shortest paths: how to walk a graph, and how to choose which traversal fits the question.

‹ Algorithms

1. How the algorithms relate

Same Graph, Three Traversal Orders BFS: A B C D E queue, by hop count DFS: A B D E C stack, deep first Dijkstra: A C B E D min-heap, by distance Graph: A-B (4), A-C (1), B-D (1), C-E (2), B-E (1) BFS reaches B and C at one hop; DFS follows A-B-D before backtracking; Dijkstra settles C (1), E (3), B (4), D (5) in order of shortest distance from A. All three are O(V + E) except Dijkstra, which is O((V + E) log V) with a binary heap.

Graph search algorithms differ mainly in the data structure that holds the frontier — the set of discovered but not yet expanded vertices. Breadth-first search uses a FIFO queue, so vertices are expanded in order of hop count; it finds shortest paths when every edge has the same cost. Depth-first search uses a stack (often the recursion stack), so it follows one branch as far as possible before backtracking; it is the basis of cycle detection, topological sorting and connected components. Dijkstra's algorithm uses a priority queue keyed by tentative distance, so it expands vertices in order of total path weight and finds shortest paths when edge weights are non-negative.

2. When to use which

ProblemAlgorithmTime
Fewest hops, unweighted shortest pathBFSO(V + E)
Reachability, cycles, topological orderDFSO(V + E)
Shortest path, non-negative weightsDijkstraO((V + E) log V)
Negative edge weightsBellman-FordO(V E)

The BFS vs DFS vs Dijkstra page runs all three on the same graph side by side. A useful mental model: Dijkstra with every edge weight equal to one behaves like BFS, and BFS with the queue replaced by a stack becomes an iterative DFS. Choosing correctly is mostly about the edge weights and whether you need distances or only structure. For dense graphs with many queries, all-pairs algorithms such as Floyd-Warshall become competitive, and A* adds a heuristic to Dijkstra when a good distance estimate to the goal exists.