The average sensitivity of a graph algorithm is a measure for the stability of the algorithm when the input graph G is perturbed by changes in edges/nodes of G. The measure is quantified by the earth mover’s distance between the algorithm’s outputs on the original and perturbed graphs. Stable algorithms (of small average sensitivity) are highly desirable. We analyze the average sensitivity of the breadth-first search (BFS) algorithm with BFS trees as outputs when the perturbation removes one edge from the input graph. It is known that for an arbitrary graph G, the average sensitivity of the BFS algorithm is \(\varTheta (|V (G)|)\) . We show that for an \(m\times n\) 2-dimensional grid graph, there is a deterministic BFS algorithm with average sensitivity at most 2, and there is a randomized BFS algorithm with average sensitivity at most 2 for \(m=n\) . We prove that for an \(n_1\times n_2\times n_3\) 3-dimensional grid, there is a deterministic BFS algorithm with average sensitivity at most \(\frac{4}{3}+\frac{2}{n}\) and there is a randomized BFS algorithm with average sensitivity at most \(\frac{2}{3}+\frac{4}{n}\) for \(n=n_1=n_2=n_3\) . These show that BFS algorithms have much better average sensitivity on grid graphs than \(\varTheta (|V(G)|)\) on arbitrary graphs.