[mcv]

> DFS or IDFS can generally use space proportional to the diameter of the graph, which is far smaller.

Maybe, but for "find the closest friend with property X" basic DFS is completely useless. It's likely to give you some distant rando with property X. Fast, sure, but not useful if you're looking for a friend.

Besides, if you have cycles in your graph, DFS also needs to keep track of which nodes you've already visited, or it's never going to end. Or use iterative deepening, which you probably want to use anyway to prevent ending up with some distant rando. Slower than BFS but consumes less memory.

> "find the ten shortest friend paths to (a unique but unknown) someone with property X, where those paths share no nodes".

Ah, but that's a completely different problem.

[towaway1138]

As above, "IDFS" == "iterative deepening DFS".

[mcv]

Yeah, I figured that out some time after I succeeded in digging through some old memory for the phrase "iterative deepening". It's been a while since I've had those classes. I do remember that at the time I didn't see the point in iterative deepening. Surely breadth first was faster than redoing the same work every time? But if you see it as a more memory-efficient way to simulate breadth-first through depth-first search, it makes sense.

Still, intuitively I'd expect that it depends a lot on the shape of your search space, the cost of your memory and the cost of traversing your network, which one is actually more efficient.

[towaway1138]

If you're generating nodes in an abstract graph (e.g., moves in chess), iterative deepening can be incredibly space-efficient, whereas BFS can rapidly consume an exponential amount of space.

As you point out, IDFS (or IDA*, etc) work far better if you have a means to avoid re-exploring the same nodes repeatedly.

Nonetheless, run-time can theoretically be greater, since you're iterating. Theoretically, though, each iteration will take N times longer than the prior, which means that the running time up to the final iteration doesn't matter that much (because it's such a small fraction of the total). The extra bookkeeping required by BFS can easily outmatch that in running time.

Definitely, it all depends.