shallow nodes and deeper nodes

Question

I found that in some tutorial the breadth first search

the shallow nodes are expanded before deeper nodes.

I am really confused what is the meaning of each of them?

Answer 1

Terms "shallow" and "deep" come from visualizing your graph with the starting node at the top: the "depth" of a node is the number of edges that you need to traverse in order to get to that node from the starting node. The statement about BFS tells you that nodes with fewer edges between them and the starting node are discovered before nodes separated from the start by more edges.

Answer 2

This means that if you compute the length L(v) of the shortest path from starting node to each individual node v in your graph, with BFS nodes with lower L(v) are always processed before nodes with higher L(v).

Simpler explanation: BFS always starts and processes all nodes that are direct neighbours of starting node. Then it processes all direct neighbours of direct neighbours of starting nodes (excluding the ones already processed) and so on.

The last nodes to be processed are the ones with the longest distance from starting node.