Why does a Breadth First Search (BFS) use more memory than Depth First Search (DFS)?

In general it may or may not depending on the particular graph.

• A depth-first search uses a stack, which contains nodes from root to the node being searched. So at most the radius of the graph.
• A breadth-first search uses a queue, which contains nodes at the front of the search. So at most all nodes at distance d.

In general graph all you can say is that it’s at most all nodes in the tree in either case. But if you have a balanced (or mostly so) k-ary tree, it’s depth, i.e. radius, will be only O(log n), while the lowest layer will contain O(n) nodes (n/2 for binary tree and even more for higher degrees). For example, in a (balanced) tree with 1023 nodes the DFS has to keep track of 10 nodes, while the BFS has to keep track of 512 nodes.

So depth-first search will only use O(log n) memory and breadth-first search will use O(n). For balanced k-ary trees; for other cases different results are possible (but for most common graphs diameter will still be significantly less than circumference).

Note that BFS doesn’t always use more memory:

• More specifically, BFS uses O(branchingFactor^maxDepth) or O(maxWidth) memory, where-as DFS only uses O(maxDepth).
• If maxWidth < maxDepth, BFS should use less memory (assuming you use similar representations for both), but this is rarely true.