Breadth-first search (BFS) and depth-first search (DFS) both explore a graph without repeatedly visiting the same vertex. They differ in which frontier vertex they explore next.
BFS explores by layers
BFS uses a queue. Start at a source vertex, mark it visited, and add it to the queue. Repeatedly remove the front vertex and enqueue its unvisited neighbors. It visits all vertices one edge away before vertices two edges away.
When all edges have equal cost, BFS finds a shortest path measured in number of edges. With an adjacency list, its time is O(V + E).
DFS follows a path
DFS uses recursion or an explicit stack. It follows one neighbor as far as possible, then backtracks to explore other branches. DFS is useful for reachability, cycle detection, connected components, and topological sorting in directed acyclic graphs.
Keep track of visited vertices
Graphs can contain cycles. Mark a vertex visited when you add it to the frontier, not only when you later process it; this prevents the same vertex from being added repeatedly. Both searches take O(V + E) time with adjacency lists.
Choose BFS when the closest or fewest-edge path matters. Choose DFS when you need to explore structure, dependencies, or paths. Weighted shortest paths need another approach, such as Dijkstra's algorithm for non-negative edge weights.