BFS vs DFS explained with one small graph

A graph is a set of nodes (dots) joined by edges (lines). Two nodes joined by an edge are called neighbours.

Let's imagine we have a graph of 5 nodes like so:

A - B
|   |
C - D - E

A's Neighbours: B, C
B's Neighbours: A, D
C's Neighbours: A, D
D's Neighbours: B, C, E
E's Neighbours: D

Let's imagine we wanted to search through the entire graph. There are two main searches we are going to talk about:

1. BFS (Breadth-first search)
2. DFS (Depth-first search)

BFS
BFS works by visiting the first node (A) and then all its neighbours, then all their neighbours, using a queue. This is essentially means that the next node to be processed is always the one that's been waiting the longest.

So, we start at A and A's neighbours are B and C. Therefore, B and C are both added to the queue of nodes that we want to look at.
Current queue: B, C

Now we are at B. B's neighbours are A and D. A has already been processed before but D has not, therefore we add only D to the queue.
Current queue: C, D

Now we are at C. C's neighbours are A and D. A has already been processed and is therefore skipped and D is already in the current queue so does not need to be re-added.
Current queue: D

Now we are at D. D's neighbours are B, C, and E. B and C have already been processed but E has not, therefore E is added to the queue.
Current queue: E

Now we are at E. E's only neighbour is D, but D has already been processed, therefore we do not add anything to the queue. The queue is now empty, therefore the BFS is complete.

Order of Traversal: A - B - C - D - E

The newest node is always added to the back in a BFS, just like a normal queue that you would experience in a shopping mall, and the node that has been waiting the longest is always processed first. This is also called FIFO (first in, first out).

DFS
DFS works by going as far down one path as it can before backing up to try others, using a stack. This means that the next node to be processed is always the newest one, the one that has been waiting the shortest amount of time. When a node has more than one new neighbour, they all go on the front of the stack together, in the same order as the neighbour list.

So, we start at A and A's neighbours are B and C. Neither has been processed, so both are added to the front of the stack.
Current stack: B, C

Now we are at B. B's neighbours are A and D. A has already been processed but D has not, therefore D is added to the front of the stack.
Current stack: D, C

Now we are at D. D's neighbours are B, C and E. B has already been processed. C is in the stack, but it hasn't been processed yet. In a DFS, that doesn't matter: D has just found C, so C should be next. Therefore C and E are both added to the front of the stack.
Current stack: C, E, C

Now we are at C. C's neighbours are A and D, and both have already been processed, so nothing is added.
Current stack: E, C

Now we are at E. E's only neighbour is D, which has already been processed, so nothing is added.
Current stack: C

Now we are at C again. But C has already been processed, so we just skip it. The stack is now empty and the DFS is complete.

Order of Traversal: A - B - D - C - E

In BFS a node that is already waiting in the queue is skipped, but in DFS it is added to the front again, because DFS always wants to process the node it found most recently. The old copy is simply skipped when it comes up. In a DFS, the newest node is always processed first, which is also called LIFO (last in, first out).

Conclusion
A BFS and a DFS can search through the exact same graph but give different orders of traversal...

BFS Order of Traversal: A - B - C - D - E
DFS Order of Traversal: A - B - D - C - E

...because they choose which node to process next in different ways. BFS uses a queue, adding new nodes to the back, so the node that has been waiting the longest goes next. DFS uses a stack, adding new nodes to the front, so the newest node goes next.

An example of when a BFS is better than a DFS is finding the shortest path (fewest edges) to a particular node. In our graph, A is 0 steps from A, B and C are 1 step away, D is 2 steps away and E is 3 steps away. BFS processed them in exactly that order: everything 1 step away before anything 2 steps away, and so on. So the first time BFS reaches a node, it has got there in the fewest steps possible.

An example of when a DFS is a natural fit is checking if a graph has a cycle (a loop). Because DFS follows one path at a time, it's easy to keep track of which node it just came from. If it reaches a node that has already been processed, and it isn't the one it just came from, it has found another way back to somewhere it has already been, which means there is a cycle. In our graph, DFS reaches C from D. C's neighbour A has already been processed and isn't D, so there is a cycle: A - B - D - C - A.